首页 > 代码库 > POJ_1485_dp
POJ_1485_dp
题目描述：
每组数据给n个点，点按一维坐标升序给出，要求划分成k块，在每一块中，取一个站，要求每个块中所有的点到站的距离的和的总和最小。
思路：
dp题，dp[i][j]表示i个点分成j块的最小距离，每一个dp[i][j]可以由前面的dp[x][j-1]推出，其中j-1 <= x <= i-1,前面j-1个分块再加上后面一块，便形成了i个点j个划分，在所有符合条件的划分中取最小值，更新dp[i][j]的值。这样的思路，我们还需要一个方法计算一个块中的距离最小值。当一个块中点的数量为奇数时，取中点为站，则距离最小，当数量为偶数时，去中间两个点的任意一个，距离最小，所以我们可以用(left+right)/2表示一个区间中的那个站点。因为结果要求输出最小值的具体划分以及站点，还需要一个pos数组储存每种情况的划分边界。
#include<cstdio>#include<iostream>#include<cstring>using namespace std;#define MAX 1<<30;int a[205],dis[205][205],dp[205][35],pos[205][35][205];int main(){ int n,K,num = 0; while(~scanf("%d%d",&n,&K) && n && K) { num++; memset(pos,0,sizeof(pos)); memset(dis,0,sizeof(dis)); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); for(int i = 1;i <= n;i++) { dis[i][i] = 0; for(int j = i+1;j <= n;j++) { int mid = (i+j)/2; for(int k = i;k < mid;k++) dis[i][j] += a[mid]-a[k]; for(int k = mid+1;k <= j;k++) dis[i][j] += a[k]-a[mid]; } } for(int i = 1;i <= n;i++) { dp[i][1] = dis[1][i]; pos[i][1][i] = 1; for(int j = 2;j <= i;j++) dp[i][j] = MAX; } for(int i = 2;i <= n;i++) { for(int j = 2;j <= min(i,K);j++) { for(int k = j-1;k <= i-1;k++) { int temp = dp[k][j-1]+dis[k+1][i]; if(temp < dp[i][j]) { dp[i][j] = temp; for(int l = 1;l <= k;l++) { pos[i][j][l] = pos[k][j-1][l]; } pos[i][j][i] = 1; } } } } printf("Chain %d\n",num); int now = 1; for(int i = 1;i <= K;i++) { int left = now; for(;!pos[n][K][now];now++); int right = now++; if (left == right) { printf("Depot %d at restaurant %d serves restaurant %d\n",i,left,left); } else { printf("Depot %d at restaurant %d serves restaurants %d to %d\n",i,(left+right)/2,left,right); } } printf("Total distance sum = %d\n\n",dp[n][K]); } return 0;}
POJ_1485_dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。