P1282 多米诺骨牌
update: 2021/7/5
针对评论区重复提到的问题进行了一波修改
优化了代码 ----------- 提高了背包部分代码的可读性
完善了思路 ----------- 采用*用2tot的背包体积寻找离体积tot最近的**，通过了评论区老哥给出的 hack 数据。在此对为我提供hack数据的老哥，以及指出我思路问题的同学表示感谢。
新代码贴在下面，原代码就不删除了，方便后来者理解评论区是怎么回事。
#include <cstdio>
#define re register int
#define in inline
#define maxn 1003
#define inf 1000006
int n;
int base,tot;
int w[maxn],v[maxn];
int dp[maxn][10*maxn];
in int read()
{
int ans=0;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) ;
for(;ch>='0'&&ch<='9';ch=getchar()) ans=ans*10+ch-'0';
return ans;
}
in int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
re i,j;
int x,y;
n=read(),base=0;
for(i=1;i<=n;i++) {
x=read(),y=read();
if(x<y){
base++;
w[i]=-1,v[i]=(y-x)*2;
tot+=y-x;
}
if(x>y){
w[i]=1,v[i]=(x-y)*2;
tot+=x-y;
}
}
for(j=1;j<=2*tot;j++) dp[0][j]=inf;//dp[0][0]=0
for(i=1;i<=n;i++){
for(j=0;j<=2*tot;j++){
if(j-v[i]>=0&&dp[i-1][j-v[i]]!=inf) dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
else dp[i][j]=dp[i-1][j];
}
}
for(i=0;i<=tot;i++){
if(dp[n][tot+i]!=inf||dp[n][tot-i]!=inf){
printf("%d\n",min(base+dp[n][tot+i],base+dp[n][tot-i]));
break;
}
}
return 0;
}
*/这其实是一道“披着狼皮的背包题”
我们只需要对状态稍作调整就可以套背包啦~~~
我们先把骨牌翻转，调整至点数大的在上面
这样，我们就能保证上方的点数一定比下方大，并且保证每翻转一 次，都能使上下的点数之差变小，而变小的点数，就是上下点数之差乘以2。
把改变的点数看成物品的体积，初始上下方的点数之差看做背包体积，不难看出背包问题的模型。
那么物品的重量是什么呢？
因为我们一开始就把点数大的放在了上面，而每放一次，翻转次数就+1。考虑：要是我后来后悔了，我发现不翻这个骨牌更好怎么办？那我会把它翻回来，那么相当于没有翻这个骨牌。
因此，一开始翻过的骨牌重量就是-1，未翻过的骨牌重量就是1（重量等价于翻转次数）
当然，上下相同的骨牌就是体积为0，重量为0的物品，因为他们无论怎么翻，都不会对上下点数差造成影响。
至此，背包的模型就出来了。这个问题被简化成：有n个物品，给出每个物品的体积v[i],他们的重量是1或-1。背包的重量为base，体积为tot，现在请把这n个物品放到背包里去，总体积不能超过tot，体积最大的情况下使得物品重量之和最小。update 2021/7/5 更改的最主要一个问题就是这个背包不是找体积最大的，而是找体积最接近tot的
其中，dp[i][j]表示前i件物品能装到体积为j的最小重量
vs[i][j]表示前i件物品能否装到j体积
上代码：```c
#include <cstdio>
int dp[1005][6005];
bool vs[1005][6005];
int w[1005];
int v[1005];
int min(int a,int b)
{
if(a<b) return a;
return b;
}
int main()
{
int n,i,j,x,y,base=0,tot=0;
//base表示背包重量，就是初始重量，初始翻转次数
scanf("%d",&n);
for(i=1;i<=n;i++) {
scanf("%d%d",&x,&y);
if(x>y){
v[i]=2*(x-y);//点数变化量看做体积
w[i]=1;
tot+=x-y;
}
if(y>x) {
v[i]=2*(y-x);
w[i]=-1;
tot+=y-x;
base++;//初始重量
}
}//用体积为v的物体装总体积为tot的背包,装的体积尽量多的情况下，总重量w最小 背包重量为base
for(i=1;i<=n;i++){
for(j=1;j<=tot;j++){
dp[i][j]=dp[i-1][j];
vs[i][j]=vs[i-1][j];
if(vs[i-1][j-v[i]]||j-v[i]==0){
if(!vs[i][j]){
dp[i][j]=dp[i-1][j-v[i]]+w[i];
vs[i][j]=1;
}
else dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
}
//printf("%d",base+dp[n][tot]);
for(i=tot;i>=1;i--) if(vs[n][i]) break;
//找到第一个用所有物品可以装到的体积
printf("%d",base+dp[n][i]);
}