题目链接：点击进入 以前也碰到过这种类型的dp，感觉就是状态不好定义和转移；原来定义状态的时候总是认为dp[i][j]就应该由dp[i-1][j-1]转移而来，这样的话就会导致需要记忆前面i-1步的所有状态，，然后就是转移方程没法写了。对于这道题，我们定义状态dp[i][j]表示前j个餐馆建立i个仓库时的最小代价，然后状态转移为dp[i][j]=dp[i-1][k-1]+cost[k][j],意思是：已经建立的前i-1个仓库负责前k-1个餐馆，然后第i个餐馆负责第k–j个餐馆，其中k<=i<=j; 然后就是这个题目还需要打印每一次的选择，我们通过最后的状态反推回去就行了。
代码如下：
;int dp[33][220],n,k;int a[222],cost[220][220];int abs(int x){if(x<0) x=-x;return x;}int cal(int i,int j){int m=(i+j)/2;int sum=0;for(int d=i;d<=j;d++)sum+=abs(a[d]-a[m]);return sum;}void print(int i,int j){if(i==1){int d=(i+j)/2;printf(“Depot %d at restaurant %d serves restaurants %d to %d\n”,i,d,i,j);return ;}else{for(int d=i;d<=j;d++){if(dp[i-1][d-1]+cost[d][j]==dp[i][j]){print(i-1,d-1);printf(“Depot %d at restaurant %d serves restaurants %d to %d\n”,i,(d+j)/2,d,j);return ;}}}}int main(){///freopen(“in.txt”,”r”,stdin);int Case=0;while(scanf(“%d%d”,&n,&k)!=EOF){if(n==0&&k==0) break;for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);memset(dp,0x3f,sizeof(dp));for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)cost[i][j]=cal(i,j);for(int i=1;i<=n;i++)dp[1][i]=cost[1][i];for(int i=2;i<=k;i++)for(int j=i;j<=n;j++){for(int d=i;d<=j;d++)dp[i][j]=min(dp[i-1][d-1]+cost[d][j],dp[i][j]);}printf(“Chain %d\n”,++Case);print(k,n);printf(“Total distance sum = %d\n\n”,dp[k][n]);} return 0;}
而不去欣赏今天就开在我们窗口的玫瑰。
