M_sea

洛谷4026 [SHOI2008]循环的债务
LuoguBZOJ分析设$f[i][j][k]$表示前$i$种面值,第一个人有$j$元,第二个人有$k$元的最小交...
扫描右侧二维码阅读全文
10
2019/01

洛谷4026 [SHOI2008]循环的债务

Luogu

BZOJ

分析

设$f[i][j][k]$表示前$i$种面值,第一个人有$j$元,第二个人有$k$元的最小交换次数。

然后枚举一下新的钱数转移过去就行了。转移太长了,写不出来qwq

注意判无解的情况。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int INF=0x3f3f3f3f;
const int w[7]={0,1,5,10,20,50,100};

int o[4][7],sum[4],cnt[7];
int f[7][1010][1010];

int main() {
    int x1=read(),x2=read(),x3=read();
    for (re int i=1;i<=3;++i)
        for (re int j=6;j>=1;--j)
            o[i][j]=read(),cnt[j]+=o[i][j],sum[i]+=o[i][j]*w[j];
    int tot=0;
    for (re int i=1;i<=3;++i) tot+=sum[i];
    memset(f,0x3f,sizeof(f)); f[0][sum[1]][sum[2]]=0;
    for (re int i=1;i<=6;++i) {
        for (re int j=0;j<=tot;++j)
            for (re int k=0;j+k<=tot;++k) {
                if (f[i-1][j][k]==INF) continue;
                chkmin(f[i][j][k],f[i-1][j][k]);
                for (re int a=0;a<=cnt[i];++a)
                    for (re int b=0;a+b<=cnt[i];++b) {
                        int c=cnt[i]-a-b;
                        int sa=j+w[i]*(a-o[1][i]);
                        int sb=k+w[i]*(b-o[2][i]);
                        int dis=(abs(a-o[1][i])+abs(b-o[2][i])+abs(c-o[3][i]))/2;
                        if (sa>=0&&sb>=0&&sa+sb<=tot)
                            chkmin(f[i][sa][sb],f[i-1][j][k]+dis);
                    }
            }
    }
    int ea=sum[1]+x3-x1,eb=sum[2]+x1-x2,ec=sum[3]+x2-x3;
    if (ea<0||eb<0||ec<0||ea+eb+ec!=tot||f[6][ea][eb]==INF)
        puts("impossible");
    else printf("%d\n",f[6][ea][eb]);
    return 0;
}
最后修改:2019 年 05 月 26 日 05 : 54 PM

2 条评论

  1. smy

    浪费空间差评(

    1. M_sea
      @smy

      开的下啊......

发表评论