分析
设\(dp[t][n][m]\)表示前\(t\)种钞票\(\text{Alice,Bob}\)分别拥有\(n,m\)元所需最小交换钞票数,
枚举\(\text{Alice,Bob}\)最后得到这种钞票的个数\(t0,t1\)
\(\text{Cynthia}\)最后便获得\(cnt-t0-t1\)张,
那么
如果\(\text{Alice}\)得到\(\text{Cynthia}\)的欠款仍然还不起\(\text{Bob}\)显然无解,
对于其余两人亦然
代码
#include <cstdio>
#include <cstring>
#define rr register
using namespace std;
const int w[6]={100,50,20,10,5,1};
int a[3],b[3][6],s[3],cnt[6],dp[7][1011][1011],inf,m;
inline signed Abs(int x){return x<0?-x:x;}
signed main(){
scanf("%d%d%d",&a[0],&a[1],&a[2]);
for (rr int i=0;i<3;++i) for (rr int j=0;j<6;++j)
scanf("%d",&b[i][j]),s[i]+=b[i][j]*w[j],cnt[j]+=b[i][j];
memset(dp,42,sizeof(dp)),dp[0][s[0]][s[1]]=0;
m=s[0]+s[1]+s[2],inf=dp[1][1][1];
for (rr int i=0;i<6;++i)
for (rr int j=0;j<=m;++j)
for (rr int k=0;k+j<=m;++k)
if (dp[i][j][k]^inf){
if (dp[i+1][j][k]>dp[i][j][k])
dp[i+1][j][k]=dp[i][j][k];
for (rr int t0=0;t0<=cnt[i];++t0)
for (rr int t1=0;t1+t0<=cnt[i];++t1){
rr int z0=j-(b[0][i]-t0)*w[i];
rr int z1=k-(b[1][i]-t1)*w[i];
rr int t2=cnt[i]-t0-t1;
if (z0>=0&&z1>=0&&z0+z1<=m){
rr int now=Abs(b[0][i]-t0)+Abs(b[1][i]-t1)+Abs(b[2][i]-t2);
if (dp[i+1][z0][z1]>dp[i][j][k]+(now>>1))
dp[i+1][z0][z1]=dp[i][j][k]+(now>>1);
}
}
}
rr int ans0=s[0]-a[0]+a[2];
rr int ans1=s[1]-a[1]+a[0];
rr int ans2=s[2]-a[2]+a[1];
if (ans0<0||ans1<0||ans2<0||dp[6][ans0][ans1]==inf)
return !printf("impossible");
else return !printf("%d",dp[6][ans0][ans1]);
}