BZOJ 1042 硬币购物

QBXT2018TG时候讲的..老早以前写的了....

    /**************************************************************
        Problem: 1042
        User: spinmry
        Language: C++
        Result: Accepted
        Time:128 ms
        Memory:2844 kb
    ****************************************************************/
    
    #include <iostream>
    using namespace std;
    
    //define
    const int maxn=100005;
    long long ans,c[4],d[4],s,f[maxn],g[maxn];
    
    void dfs(int x,int k,long long sum){
        if(sum<0)return;
        if(x==4){
            if(k&1)ans-=f[sum];
            else ans+=f[sum];
            return;
        }
        dfs(x+1,k+1,sum-(d[x]+1)*c[x]);
        dfs(x+1,k,sum);
    }
    
    //main
    int main(){
        ios::sync_with_stdio(false);
        f[0]=1;
        for(int i=0;i<4;i++)
            cin>>c[i];
        for(int k=0;k<4;k++)
            for(int i=c[k];i<=maxn;i++)
                f[i]=f[i]+f[i-c[k]];
        int tot=0;
        cin>>tot;
        while(tot--){
            for(int i=0;i<4;i++)
                cin>>d[i];
            cin>>s;
            ans=0;
            dfs(0,0,s);
            cout<<ans<<endl;
    
        }
        return 0;
    }