P1450

Aryper · 2021-08-09 10:13:19 · 个人记录

[HAOI2008]硬币购物

然后发现多重背包并不可做。

接着有了一种神奇的做法。

我们先按照完全背包预处理，然后容斥。

比如说现在的 f(s) ，它包含着很多可能，其中有合法的，有不合法的。

我们现在只针对第一种硬币来看怎样取出合法方案或剔除不合法方案。

显然，f(s-c_1(d_1+1)) 种方案是不合法的。

可以想象，我们从 f(s-c_1(d_1+1)) 转移到 f(s) ，确保了我们的第一种硬币使用了大于等于 (d_1+1) 个，所以不论 f(s-c_1(d_1+1)) 中包含了第一种硬币怎样的使用情况，转移到 f(s) 时全部都是不合法的。

然后我们可以把四种硬币的不合法方案全部减掉，发现有一些重复了。比如说第一种硬币不合法的方案与第二种硬币不合法的方案有交集，但减去了两次，这一部分就要再加上来。

然后就是普通容斥，我们把重复的方案加上后，又有重复了重复的方案，还要再减去，以此类推，直到恰好覆盖整个 Venn 图。

这样下来时间复杂度就够了。

然后一共有 15 种可能，我们可以用暴力枚举，也可以用一点二进制分解的技巧。

二进制数 1~15 ，其实包含了共 4 位上，每一位 0/1 ，但至少有一位是 1 的全部可能，那么把每一位看作是否考虑某一种硬币，按 1 的个数的奇偶确定加减，就可以较为优美地容斥了。

代码（二进制容斥）：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,ans,s,tmp,cnt;

ll f[N+5],d[5],c[5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    for(ll i=1;i<=4;i++) c[i]=read();
    n=read();

    f[0]=1;
    for(ll i=1;i<=4;i++) {
        for(ll j=c[i];j<=1e5;j++) {
            f[j]+=f[j-c[i]];
        }
    }

    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=4;j++) {
            d[j]=read();
        }
        s=read();
        ans=f[s];
        for(ll j=1;j<=15;j++) {
            tmp=s;cnt=1;
            for(ll k=1;k<=4;k++) {
                if(j>>(k-1)&1) {
                    tmp-=(d[k]+1)*c[k];
                    cnt=-cnt;
                }
            }
            if(tmp>=0) ans+=cnt*f[tmp];
        }
        write(ans);putchar('\n');
    }

    return 0;
}

代码（暴力）：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,ans,s,tmp;

ll f[N+5],d[5],c[5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    for(ll i=1;i<=4;i++) c[i]=read();
    n=read();

    f[0]=1;
    for(ll i=1;i<=4;i++) {
        for(ll j=c[i];j<=1e5;j++) {
            f[j]+=f[j-c[i]];
        }
    }

    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=4;j++) {
            d[j]=read();
        }
        s=read();
        ans=f[s];
        for(ll j=1;j<=4;j++) {
            tmp=s-(d[j]+1)*c[j];
            if(tmp>=0) ans-=f[tmp];
        }
        for(ll j=1;j<=4;j++) {
            for(ll k=j+1;k<=4;k++) {
                tmp=s-(d[j]+1)*c[j]-(d[k]+1)*c[k];
                if(tmp>=0) ans+=f[tmp];
            }
        }
        for(ll j=1;j<=4;j++) {
            for(ll k=j+1;k<=4;k++) {
                for(ll p=k+1;p<=4;p++) {
                    tmp=s-(d[j]+1)*c[j]-(d[k]+1)*c[k]-(d[p]+1)*c[p];
                    if(tmp>=0) ans-=f[tmp];
                }
            }
        }
        tmp=s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[3]+1)*c[3]-(d[4]+1)*c[4];
        if(tmp>=0) ans+=f[tmp];
        write(ans);putchar('\n');
    }

    return 0;
}