考虑 $dp$，设 $f[i][j][k]$ 表示考虑了前 $i$ 种面值的钱，$Alice$ 现在有共 $j$ 元，$Bob$ 现在共有 $k$ 元时，的最少交换次数
那么 $Cynthia$ 的状态可以由总和减去 $Alice$ 和 $Bob$ 的状态得到
然后枚举每一种钱，枚举初末此种钱的张数，然后就可以转移，因为有很多状态是不合法的所以复杂度能过
枚举钱从大到小枚举可以使得不合法状态比较多
#include#include #include #include #include using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=1007,w[7]={ 0,100,50,20,10,5,1},INF=1e9+7;int x1,x2,x3,a[9],b[9],c[9],sa,sb,sc,sum,cnt[9];int f[9][N][N];int main(){ x1=read(),x2=read(),x3=read(); for(int i=1;i<=6;i++) a[i]=read(),sa+=a[i]*w[i]; for(int i=1;i<=6;i++) b[i]=read(),sb+=b[i]*w[i]; for(int i=1;i<=6;i++) c[i]=read(),sc+=c[i]*w[i]; for(int i=1;i<=6;i++) cnt[i]=a[i]+b[i]+c[i]; memset(f,0x3f,sizeof(f)); f[1][sa][sb]=0; sum=sa+sb+sc; for(int i=1;i<=6;i++)//枚举第i种钱 for(int j=0;j<=sum;j++)//枚举Alice的状态 for(int k=0;j+k<=sum;k++)//枚举Bob的状态 { if(f[i][j][k]>INF) continue;//判断不合法状态 for(int p=0;p<=cnt[i];p++)//枚举结束后Alice有多少此钞票 for(int q=0;p+q<=cnt[i];q++)//枚举结束后Bob有多少此钞票 { int ta=j+(p-a[i])*w[i],tb=k+(q-b[i])*w[i], tc=sum-sa-sb+(cnt[i]-p-q-c[i])*w[i] //结束后Alice,Bob,Cynthia的总钱数分别为ta,tb，tc if(ta<0||tb<0||tc<0) continue; f[i+1][ta][tb]=min(f[i+1][ta][tb], f[i][j][k]+(abs(p-a[i])+abs(q-b[i])+abs(cnt[i]-p-q-c[i]))/2 ); //记得转移张数是总张数除以2 } } sa-=x1,sb+=x1; sb-=x2,sc+=x2; sc-=x3,sa+=x3; if(sa<0||sb<0||sc<0||f[7][sa][sb]>INF) { printf("impossible\n"); return 0; } printf("%d\n",f[7][sa][sb]); return 0;}