题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1227
题意:一维坐标上有n个点,位置已知,选出k(k <= n)个点,使得所有n个点与选定的点中最近的点的距离总和最小,求出最小值。
思路:
将点i的距离记为为dis[i],从i到j选出一点使此段距离和最小,则此点坐标为dis[(i + j) / 2]
cost[i][j]为从i到j选出一点距离和的最小值。则求cost[i][j]的代码如下:
cost[i][j] = 0;
for(int k = i; k <= j; k++){
cost[i][j] += abs(dis[(i + j)/2] - dis[k]);
}
dp[i][j]表示从1到i选择j个点的最小值,则状态转移方程如下:
dp[i][j] = min(dp[k][j - 1] + cost[k + 1][i]) (j - 1 <= k <i)
代码如下,注意边界情况的处理,表示我也很头疼边界情况
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<queue> #include<vector> #include<algorithm> using namespace std; typedef long long LL; const int N = 208; LL dp[N][32], cost[N][N]; int dis[N]; int main(){ int n, m, cs = 0; while(~scanf("%d %d", &n ,&m) && n && m ){ for(int i = 1; i <= n ; i++){ scanf("%d", &dis[i]); } memset(cost, 0x3F, sizeof(cost)); memset(dp, 0x3F, sizeof(dp)); for(int i = 1; i <= n ; i++){ for(int j = i; j <= n ;j++){ cost[i][j] = 0; for(int k = i; k <= j; k++){ cost[i][j] += abs(dis[(i + j)/2] - dis[k]); } } } for(int i = 1; i <= n; i++){ dp[i][1] = cost[1][i]; } for(int j = 2; j <= m ; j++){ for(int i = j; i <= n; i++){ for(int k = j - 1; k < i; k++){ dp[i][j] = min(dp[i][j], dp[k][j - 1] + cost[k + 1][i]); } } } cs++; printf("Chain %d Total distance sum = %I64d ",cs,dp[n][m]); } return 0; }