[bzoj1042][HAOI2008][硬币购物] (容斥原理+递推)

Description

　　硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s
i的价值的东西。请问每次有多少种付款方法。

Input

　　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

Output

　　每次的方法数

Sample Input

Sample Output

Solution

先递推一下哈

用递推式f[s]+=f[s-c[i]]，求出没有个数限制情况下达到价值s的方案数

那么，有限制的方案数=f[s]-超过硬币1限制的方案数-超过硬币2限制的方案数-超过硬币3限制的方案数-超过硬币4限制的方案数+超过硬币1、2限制的方案数+超过硬币1、3限制的方案数+超过硬币1、4限制的方案数+。。。+超过硬币1、2、3、4限制的方案数

那么，对于超过情况

设s[i]代表第i种硬币的限制个数，c[i]代表第i种硬币的价值

我们只考虑超过s[i]+1的情况，剩下tot-c[i]*(s[i]+1)的话就*分配

很科学吧

#include <stdio.h>

#define MaxN 100010

#define MaxBuf 1<<22

#define L long long

#define Blue() ((S==T&&(T=(S=B)+fread(B,1,MaxBuf,stdin),S==T))?0:*S++)

char B[MaxBuf],*S=B,*T=B;

template<class Type>inline void Rin(Type &x){

    x=0;int c=Blue();bool b=0;

    for(;c<48||c>57;c=Blue())

        if(c==45)b=1;

    for(;c>47&&c<58;c=Blue())

        x=(x<<1)+(x<<3)+c-48;

    x=b?-x:x;

}

int c[4],s[4],tar,kase;

L f[MaxN],ans;

void dfs(int x,int y,int sum){

    if(sum<0)

        return;

    if(x==4){

        ans+=y&1?-f[sum]:f[sum];

        return;

    }

    dfs(x+1,y,sum);

    dfs(x+1,y+1,sum-c[x]*(s[x]+1));

}

#define FO(x) {freopen(#x".in","r",stdin);}

int main(){

    FO(bzoj1042);

    for(int i=0;i<4;i++)

        Rin(c[i]);

    f[0]=1;

    for(int i=0;i<4;i++)

        for(int j=c[i];j<=100000;j++)

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

    Rin(kase);

    while(kase--){

        for(int i=0;i<4;i++)

            Rin(s[i]);

        Rin(tar);

        ans=0;

        dfs(0,0,tar);

        printf("%lld\n",ans);

    }

    return 0;

}

秒客网