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]