九度OJ 教程99 动态规划之《搬寝室》

题目地址：http://ac.jobdu.com/problem.php?cid=1040&pid=98

//九度OJ 教程99 动态规划之《搬寝室》//http://ac.jobdu.com/problem.php?cid=1040&pid=98#include<stdio.h>#include<string.h>#include<stdlib.h>#define MAXS 2002int min(int a,int b)//该函数保证在a、b俩数最多有一个负数（俩大数相加导致的负数）存在的情况下，返回一个正的较小的数。{if(b<0)return a;//b<0是为了防止俩大数相加出现负数而导致的误判。if(b<a)return b;return a;}int list[MAXS],dp[MAXS][MAXS];int cmp(const void *a,const void *b)//按照从小到大排序。{int *aa=(int *)a,*bb=(int *)b;return *aa-*bb;}int main(){int k,n,i,j;while(~scanf("%d %d",&n,&k)){memset(list,0x7f,MAXS*sizeof(int));memset(dp,0x7f,MAXS*MAXS*sizeof(int));memset(dp,0,MAXS*sizeof(int));//只把第一行清零。即：任何前j个物品取i=0对后的疲劳度都是0for(j=1;j<=n;j++)scanf("%d",&list[j]);qsort(list+1,n+1,sizeof(list[0]),cmp);for(i=1;i<=k;i++){for(j=2*i;j<=n;j++){dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(list[j]-list[j-1])*(list[j]-list[j-1]));//此处与大神代码不同。我的思路是不用判断j==2*i。因为如果j==2*i，则j-1必小于2*i。根据上面的memset()函数，dp[i][2*i-1]这个值非常大，已经大于2000*2^16这个值了（2000是n的规模，2^16是任意俩重量相减再平方的疲劳值的最大值。）。而在这俩嵌套循环中，j的初值就设置成了2*i，下面修改也只是修改dp[i][j]的值，j只能++而不会减少，故没有机会修改dp[i][2*i-1]这个数的值。由于求的是min()，那么大的一个dp[i][2*i-1]，本身就会被min函数搞掉。故，我认为，不用判断相等与否，依然可行。一句话总结：我理解的大神代码的意思为“如果j等于了2*i，那么dp[i][j-1]的值绝不能赋给dp[i][j]”，而我的意思是“由于上面的限定，dp[i][j]通过min函数赋值，则永远不会继承到前面dp[i][2*i-1]这个值。”}//结果竟然wrong了……我想不通……}printf("%d\n",dp[k][n]);}return 0;}