自动搬运

查看原文

来自洛谷，原作者为

	D_14134 AFOing。。。

搬运于2025-08-24 21:55:41，当前版本为作者最后更新于2019-01-21 15:38:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

恶心的dp

我们考虑这个问题其实就是一开始A,B,C分别有sa,sb,sc的钱，总共n元，经过一波py，目标状态的A,B,C分别有ea,eb,ec的钱。问最少需要交换几张钱。

我们一种面额一种面额的考虑，显然不同面额之间互不影响.（而且你考虑的顺序其实可以是任意的，所以你可以按照张数从小到大来做。）

我们考虑dp，f[k][i][j]，表示考虑前k种面额，A现在有i元，B现在有j元最少需要交换几张。

(显然此时C有n-i-j元，不用记录这一维状态)我们现在考虑第k+1种面额，枚举py之后A有a张，B有b张，c有tot-a-b张，能转移到的状态可以直接计算，交换张数也可以直接计算。

code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1050
#define maxm 10
using namespace std;
int X1,X2,X3,tot,cnt[maxm],sum[maxn];
int num[maxm][maxm],val[maxm]={0,100,50,20,10,5,1};
int f[maxm][maxn][maxn],inf,ans;
int main(){
	scanf("%d%d%d",&X1,&X2,&X3);
	for(int i=1;i<=3;i++){
		for(int j=1;j<=6;j++){
			scanf("%d",&num[i][j]);
			sum[i]+=num[i][j]*val[j];
			tot+=num[i][j]*val[j];
			cnt[j]+=num[i][j];
		}
	}
	memset(f,127,sizeof(f));
	f[0][sum[1]][sum[2]]=0;inf=ans=f[1][1][1];
	for(int i=1;i<=6;i++) for(int j=0;j<=tot;j++) for(int k=0;k+j<=tot;k++)
		if(f[i-1][j][k]!=inf) {for(int x1=0;x1<=cnt[i];x1++)
			for(int x2=0;x1+x2<=cnt[i];x2++){
				int now1=j-(num[1][i]-x1)*val[i];
				int now2=k-(num[2][i]-x2)*val[i];
				int x3=cnt[i]-x1-x2;
				if(now1>=0&&now2>=0&&now1+now2<=tot){
					int w=abs(num[1][i]-x1)+abs(num[2][i]-x2)+abs(num[3][i]-x3);
					f[i][now1][now2]=min(f[i][now1][now2],f[i-1][j][k]+(w>>1));
				}
			}
		}
	int S1=sum[1]-X1+X3,S2=sum[2]-X2+X1,S3=sum[3]-X3+X2;
	for(int i=0;i<=6;i++)ans=min(ans,f[i][S1][S2]);
	if(S1<0||S2<0||S3<0||ans==inf)printf("impossible");
	else printf("%d",ans);
	return 0;
}