爱华网| 描述 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");}
