题意：输入n，k，然后输入n个数，这n个数表示距离起点的距离，现在要选取k个点，使得距离和最小。
分析：我们求的是从n个点中选取k个点使得距离最小，即dp[n][k],那么dp[n][k]为dp[n-1][k-1]+sum[n][n],dp[n-2][k-1]+sum[n-1][n],dp[n-3][k-1]+sum[n-2][n]....dp[1][k-1]+sum[2][n]之间的最小值。
其中sum[x][y]表示从x点到y点在此区间选取一个点的最短距离（如果是个数是单数的话，选取中间那个点，偶数的话选取中间两个哪个都行）
记忆化搜索：
#include <iostream> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <stack> using namespace std; const int oo = 1e9; int a[222]; int dp[222][33]; int sum[222][222]; int DFS(int n, int k) { if(n<0||k<0) return oo; if(dp[n][k]!=-1) return dp[n][k]; if(k>=n) { dp[n][k] = 0; return 0; } dp[n][k] = oo; for(int i=1; i<=n; i++) { dp[n][k] = min(dp[n][k], DFS(i-1, k-1)+sum[i][n]);//为前n个点建立k个点，可以由前1到n-1个点建立k-1个点推得，找到最优解。 } return dp[n][k]; } int main() { int n, m; int kk = 1; while(scanf("%d%d", &n, &m), n+m) { a[0] = 0; for(int i=1; i<=n; i++) { scanf("%d", &a[i]); } for(int i=1; i<=n; i++) { sum[i][i] = 0; for(int j=i+1; j<=n; j++) { sum[i][j] = sum[i][j-1]+a[j]-a[(i+j)/2];//sum[i][j]表示在i，j之间选取一个点，消耗的最短距离（如果是单数的话，选取中间那个点，偶数的话选取中间两个哪个都行） } } memset(dp, -1, sizeof(dp)); int ans = DFS(n, m); printf("Chain %d\n", kk++); printf("Total distance sum = %d\n\n", ans); } return 0; }
dp
#include <iostream> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <stack> using namespace std; const int oo = 1e9; int a[222]; int dp[222][33]; int sum[222][222]; int main() { int n, m; int kk = 1; while(scanf("%d%d", &n, &m), n+m) { a[0] = 0; for(int i=1; i<=n; i++) { scanf("%d", &a[i]); } for(int i=1; i<=n; i++) { sum[i][i] = 0; for(int j=i+1; j<=n; j++) { sum[i][j] = sum[i][j-1]+a[j]-a[(i+j)/2]; } } for(int i=0; i<=n; i++) { for(int j=0; j<=m; j++) { dp[i][j] = oo; } } dp[0][0] = 0; for(int i=1; i<=n; i++) { for(int k=1; k<=m; k++) { for(int j=0; j<i; j++)//此层循环和上层循环哪个在外面都可以，因为dp[i][k]只和 dp[1][k-1]到dp[i-1][k-1]之间的有关 { dp[i][k] = min(dp[i][k], dp[j][k-1]+sum[j+1][i]);//枚举从1到i-1之间的状态，进行更新dp[i][k]的值 } } } printf("Chain %d\n", kk++); printf("Total distance sum = %d\n\n", dp[n][m]); } return 0; }
原文：http://www.cnblogs.com/mengzhong/p/5414100.html