多米诺骨牌解题报告【p1282】

一个改动的背包问题，每个骨牌都有翻或不翻两种情况，因为如果当前的差值不一定能保证最终的差值最小，所以不能用贪心做，而状态转移数组里存的要是最小翻转次数。 **特**~~殊~~**技**~~巧~~：当要使用负的数组下标时，将数组平移到正的（最好$\mathrm{define}$一个$N$，更方便看） 总结：当有两个（或相似）状态时，且单个个数较多的，应该使用背包思想 ```cpp #include<cstdio> #include<cstring> int min(int x,int y){return x<y?x:y;} int abs(int x) { if(x>=0) return x; return -x; } int f[1001][10001];//f[i][j]表示前i个差值为j-5000时的最小反转次数 int up[1001],down[1001]; int main() { memset(f,0x3f,sizeof(f)); f[0][5000]=0; int n,m,minn=9999999; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&up[i],&down[i]); for(int i=1;i<=n;i++)//做到第i个骨牌 for(int j=-5000;j<=5000;j++)//j是实际差值 { if(j-(up[i]-down[i])+5000>=0&&f[i-1][j-(up[i]-down[i])+5000]<0x3f3f3f3f) f[i][j+5000]=min(f[i][j+5000],f[i-1][j-up[i]+down[i]+5000]+1); if(j-(down[i]-up[i])+5000>=0&&f[i-1][j-(down[i]-up[i])+5000]<0x3f3f3f3f) f[i][j+5000]=min(f[i][j+5000],f[i-1][j-down[i]+up[i]+5000]); } for(int i=0;i<=5000;i++) if(f[n][5000-i]<0x3f3f3f3f||f[n][5000+i]<0x3f3f3f3f) { printf("%d\n",min(f[n][5000-i],f[n][5000+i])); return 0; } return 0; } ```