[HAOI2008]硬币购物

题目链接：Click here

Solution:

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

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

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

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

Code:

#include
#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>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\n",ans);
}
signed main(){
    for(int i=1;i<=4;i++) c[i]=read();
    prepare();
    int t=read();
    while(t--) solve();
    return 0;
}