链接：Luogu-P1282
审题
一个骨牌转与不转，改变了两行之间的差值。要求用最少的旋转次数，达到最小差值。
分析
可以看出这是个背包：到底是把上下差值还是旋转次数作体积呢？旋转与否建立了不同差值之间的联系，所以直接以差值为体积即可。定义$f(i)$为上面一行和减去下面一行和的值为$i$的时候还需要的最小旋转次数。则有：$f(i)=\min\{f(i+a),f(i-a)+1\}$
代码
注意数组下标不能为负。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000,OFST=30000,INF=0x3f3f3f3f;
int N,A[MAXN+10],B[MAXN+10],opt[MAXN+10][OFST*2+10];
int MaxD,MinD;
int main() {
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d %d",&A[i],&B[i]);
memset(opt,0x3f,sizeof(opt));
opt[0][OFST]=0;
MaxD=20000;MinD=-20000;
for(int i=1;i<=N;i++) {
int dif=A[i]-B[i];
for(int j=MaxD;j>=MinD;j--)
opt[i][j+OFST]=min(opt[i-1][j-dif+OFST],opt[i-1][j+dif+OFST]+1);
}
for(int i=0;i<=5*N+10;i++) {
int Ans=INF;//注意这里，正负对称位置都有解的时候，输出翻转数最小的，不能写成if-else if，也就是随便输出一个！
if (opt[N][i+OFST]<INF-10)
Ans=min(opt[N][i+OFST],Ans);
if (opt[N][-i+OFST]<INF-10)
Ans=min(opt[N][-i+OFST],Ans);
if (Ans<INF-10) {
printf("%d\n",Ans);
return 0;
}
}
return 0;
}
