[HAOI2008]硬币购物

题目链接：Click here

Solution:

看题，先考虑多重背包，发现复杂度不太可行，再来考虑完全背包

我们可以先用完全背包预处理出没有限制的状态下，(f[s])表示(s)价值的方案数

再来考虑有一个限制的情况怎么做，对于物品(i)，我们最多只能用(d[i])次，那么我们硬点它用了(d[i]+1)次

也就是说，(f[s-(d[i]+1) imes c[i]])的这些方案是不合法的，考虑到这样可能会重复减，那么容斥即可

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+11;
int c[5],d[5],f[N],ans;
int read(){
    long long x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void prepare(){
    f[0]=1;
    for(int i=1;i<=4;i++)
        for(int j=c[i];j<N;j++)
            f[j]+=f[j-c[i]];
}
void solve(){
    for(int i=1;i<=4;i++) d[i]=read();
    int Val=read();ans=f[Val];
    for(int i=1;i<16;i++){
        int re=0,tmp=0;
        for(int j=0;j<4;j++)
            if((i>>j)&1) tmp+=(1+d[j+1])*c[j+1],++re;
        if(tmp>Val) continue;
        if(re&1) ans-=f[Val-tmp];
        else ans+=f[Val-tmp];
    }printf("%lld
",ans);
}
signed main(){
    for(int i=1;i<=4;i++) c[i]=read();
    prepare();
    int t=read();
    while(t--) solve();
    return 0;
}