题解 P4026 【[SHOI2008]循环的债务】

· · 题解

恶心的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;
}