思路

注意到这道题中A,B,C拥有的钱的最终状态是可以确定的

将不同种类的钱分开讨论，设\(f[k][i][j]\)表示考虑了前k种钱，A有i元，B有j元的最小交换次数，初值\(f[0][0][0]=0\)，目标是\(f[6][lasta][lastb]\)，\(last\)表示最终的钱数，模拟一下很容易转移，，，然而BZOJ上面好像会TLE不知道为什么，洛谷上可以过

#include
    
     #define re register#define Min(x,y) ((x)<(y) ? (x):(y))#define Abs(x) ((x)>0 ? (x):(-(x)))using namespace std;int x[4],sump[4],summ[7];int a[4][7],val[7]={0,100,50,20,10,5,1};int f[7][1002][1002];//前k种钱，A有i元，B有j元的次数 template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}int main(){    for(int i=1;i<=3;++i) read(x[i]);    for(int i=1;i<=3;++i)    {        for(int j=1;j<=6;++j)        {            read(a[i][j]);            sump[i]+=a[i][j]*val[j];            summ[j]+=a[i][j];        }    }    //算出最后A,B,C的钱     sump[1]=sump[1]-x[1]+x[3];    sump[2]=sump[2]-x[2]+x[1];    sump[3]=sump[3]-x[3]+x[2];    int S=0;    memset(f,100,sizeof(f));    f[0][0][0]=0;    for(re int k=0;k<6;++k)    {        for(re int i=0;i<=S;++i)        {            for(re int j=0;i+j<=S;++j)            {                if(f[k][i][j]<100000000)                for(re int o=0;o<=summ[k+1];++o)                {                    for(re int p=0;p+o<=summ[k+1];++p)                    {                        re int cc=Abs(o-a[1][k+1])+Abs(p-a[2][k+1])+Abs(summ[k+1]-o-p-a[3][k+1]);                        f[k+1][i+o*val[k+1]][j+p*val[k+1]]=Min(f[k+1][i+o*val[k+1]][j+p*val[k+1]],f[k][i][j]+(cc>>1));                    }                }            }        }        S+=summ[k+1]*val[k+1];    }    if(sump[1]<0||sump[2]<0||sump[3]<0||f[6][sump[1]][sump[2]]>100000000) cout<<"impossible"<