DP–乡村邮局问题-Post Office
Sample Input
10 5
1 2 3 6 7 9 11 22 44 50
Sample Output
9
python 版本
def arrange(arr, k): n = len(arr) arr = [0] + arr w = [[0] * (n+1) for _ in range(n+1)] # print(w) dp = [[0] * (n+1) for _ in range(n+1)] for i in range(n+1): for j in range(i+1, n+1): # print(i, j) w[i][j] = w[i][j-1] + arr[j] - arr[(i+j)//2] for i in range(1, n+1): dp[i][1] = w[1][i] #在1-i之间建立一个邮局时的最短距离 dp[i][i] = 0 for i in range(1, n+1): zz = min(k, i) for j in range(2, zz+1): dp[i][j] = float("inf") # print(i-1, j) for z in range(j,i): # print(k,k+1,j) dp[i][j] = min(dp[i][j], dp[z][j-1] + w[z+1][i]) return dp[n][k]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)