bzoj1042硬币购物——递推+容斥

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1042

递推，再用容斥原理减掉多余的，加上多减的……(dfs)即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

ll c[],tot,d[],s,f[];

void dfs(ll x,ll y,ll z)//第x种硬币，选了y个，体积z

{

    if(x>)

    {

        if(y&)f[s]-=f[z];

        else if(y)f[s]+=f[z];

        return;

    }

    dfs(x+,y,z);

    if(c[x]*(d[x]+)<=z)

        dfs(x+,y+,z-c[x]*(d[x]+));

}

int main()

{

    scanf("%lld%lld%lld%lld%lld",&c[],&c[],&c[],&c[],&tot);

    while(tot--)

    {

        memset(f,,sizeof f);

        scanf("%lld%lld%lld%lld%lld",&d[],&d[],&d[],&d[],&s);

        f[]=;

        for(ll i=;i<=;i++)

            for(ll j=c[i];j<=s;j++)//从c[i]开始！

                f[j]+=f[j-c[i]];

        dfs(,,s);

        printf("%lld\n",f[s]);

    }

    return ;

}