[SHOI2008]循环的债务

DP 背包

题面

戳我

解析

感觉比较套路。
当然前提是注意到各币值互不影响。

那就简单了。
设$f[i][j][k]$表示到第$i$种币值，$A$有$i$元，$B$有$j$元。显然钱的总量固定，$C$的钱数可以顺带算出来。
这样起始状态和最终状态都知道。

然后枚举下他们交易完后各剩多少张该币值的钱，直接转移即可。
若设$x,y,z$分别表示$A,B,C$钱数的变化量，那么实际交换次数为$(\Delta x+\Delta y+\Delta z)\div 2$。（这个手算下就出来了）。

如果要过$Bzoj$，需要倒着枚举币值。因为币值越大，能有效转移到后面去的状态就越少，很容易被$continue$掉。
复杂度应该是$O(6*1000^2*30^2=5.4*10^9)$，但是很难跑满。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
using namespace std;
int X1,X2,X3,f[2][1005][1005],num[5][10],snum[10],ss[5],sum,val[10]={0,1,5,10,20,50,100};
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  X1=gi();X2=gi();X3=gi();
  for(re int i=1;i<=3;++i)
    for(re int j=6;j>=1;--j)
    {
      num[i][j]=gi();
      snum[j]+=num[i][j];
      ss[i]+=val[j]*num[i][j];
    }
  sum=ss[1]+ss[2]+ss[3];
  memset(f[0],63,sizeof(f[0]));
  f[0][ss[1]][ss[2]]=0;
  for(re int i=1;i<=6;++i)
  {
    re int now=i&1,pre=now^1;
    memset(f[now],63,sizeof(f[now]));
    for(re int j=0;j<=sum;++j)
    for(re int k=0;k<=sum-j;++k)
    {
      if(f[pre][j][k]>1e9) continue;
      for(re int n=0;n<=snum[i];++n)
      for(re int m=0;m<=snum[i]-n;++m)
      {
        re int A=j+(n-num[1][i])*val[i],B=k+(m-num[2][i])*val[i];
        if(A>=0&&B>=0&&A<=1000&&sum-A-B>=0)
      {
        re int w=abs(n-num[1][i])+abs(m-num[2][i])+abs(num[1][i]+num[2][i]-n-m)>>1;
        f[now][A][B]=min(f[now][A][B],f[pre][j][k]+w);
      }
      }
    }
  }
  re int las1=ss[1]-X1+X3,las2=ss[2]+X1-X2;
  if(las1<0||las2<0||sum-las1-las2<0||f[0][las1][las2]>1e9) puts("impossible");
  else printf("%d\n",f[0][las1][las2]);
  return 0;
}