描述 Description | |||
【问题描述】 多米诺骨牌有上下2个方块组成,每个方块中有1~6个点。现有排成行的n个多米诺骨牌如图8-1所示。 编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。 对于图8-1中的例子,只要将最后一个多米诺骨牌旋转180°,可使上下2行点数之差为0。 【输入】 输入文件的第一行是一个正整数n(1≤n≤1000),表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数,表示多米诺骨牌上下方块中的点数a和b,且1≤a,b≤6。 【输出】 输出文件仅一行,包含一个整数。表示求得的最小旋转次数。 【样例输入】 4 6 1 1 5 1 3 1 2 【样例输出】 1 | |||
时间限制 Time Limitation | |||
各个测试点1s | |||
======================================================题目分析:一眼看上去,像是个背包。实际上,也确实是背包,而且是01背包。但是一不留神就会错误。以下总结几个易错点。易错点一:没有考虑到负数情况,保留状态时按差值的绝对值保留,然而这样在0附近时易出错,因为是01背包,枚举时必须保证单调性。解决方法,用一个maxf表示差值中负值的绝对值之和是多少。记录时f[i]统一记录成f[i+maxf],这样就不会出错。易错点二:更新最小值时,不更新比当前已记录最小值更大的值。这样是错误的。如果是这样写,相当于一个贪心。而实际上如果不翻转时差值是2,翻转第一块能变成4,在翻转第一块的基础上翻转第二块能使差值变成0,这样的数据如果用贪心就不会是最优解(最后记录的最优值会是2)。易错点三:for循环时应该考虑正负数,循环顺序是不同的。因为要保证是01背包,循环顺序不能错。=================================================================================我的程序:#include<stdio.h>#include<stdlib.h>inti,j,k,f[12001]={0},a[1001],n,maxz=0,maxf=0,now=0;//maxf记录负数的绝对值之和,now表示不翻转的差值,a[i]表示第i块骨牌上下点数之差,f[i]表示达到差值为i-maxf的状态所需的最小步数int main(){ scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&j,&k); a[i]=j-k; if (a[i]<0) maxf-=a[i]; else maxz+=a[i]; now+=a[i]; } f[now+maxf]=1;//这里先将最小步数统一加上一,方便判断这个状态是否达到过 for(i=0;i<n;i++) if(a[i]>0) //分情况讨论,正负值的枚举状态方向相反,重要! { for(j=2*a[i];j<=maxz+maxf;j++) if(f[j]>0&&(f[j-2*a[i]]==0||f[j-2*a[i]]>f[j]+1)) f[j-2*a[i]]=f[j]+1;//如果上个状态可以达到,并且满足递推关系(以前不能达到本状态,或以前达到本状态的的最小步数小雨上个状态最小步数+1),则更新f[f-2*a[i]]。注意翻转一次是改变2*a[i]的差值。 } elseif (a[i]<0) { for(j=maxz+maxf+2*a[i];j>=0;j--) if(f[j]>0&&(f[j-2*a[i]]==0||f[j-2*a[i]]>f[j]+1))//同上 f[j-2*a[i]]=f[j]+1; } i=maxf; j=maxf; while(f[i]==0&&f[j]==0)//从差值为0开始找,同时向两边扩展,直到达到一个可以达到的状态,这个状态就是最优状态(最小差值) { i++; j--; } if (f[i]==0)printf("%dn",f[j]-1); //因为之前统一加上了一,所以要减一输出 elseif (f[j]==0||f[i]<=f[j])printf("%dn",f[i]-1); system("pause");}