本文共 1113 字，大约阅读时间需要 3 分钟。
WA
1. 写出了 dist[][] 数组和 minDist() 函数, 实现了 minDist 函数但最终却是使用了 dist 数组
不一致
代码
#include #include #include #include #include #include #include #include #include #include #define MIN(x,y) (x)<(y)?(x):(y)using namespace std;int pos[10010];int dp[10010][40];int minDist(int i, int j) { if(i >= j) return 0; int mid = (i+j)/2; int sum = 0; for(int k = i; k <= j; k ++) { sum += abs(pos[k]-pos[mid]); } return sum;}int solve_dp(int v, int p) { memset(dp, 0x3f, sizeof(dp)); // init for(int i = 0; i <= p; i ++) dp[0][i] = 0; for(int i = 1; i <= v; i ++) { for(int j = 1; j <= p; j ++) { for(int k = 0; k < i; k ++) { dp[i][j] = min(dp[i][j], dp[k][j-1] + minDist(k+1,i)); } } } return dp[v][p];}int main() { freopen("C:\\Users\\vincent\\Dropbox\\workplacce\\joj\\test.txt", "r", stdin); int V, P; while(scanf("%d%d", &V, &P) != EOF) { for(int i = 0; i < V; i ++) { scanf("%d", pos+i+1); } int res = solve_dp(V, P); printf("%d\n", res); } return 0;}
转载于:https://www.cnblogs.com/zhouzhuo/p/3678525.html