BZOJ 1042：[HAOI2008]硬币购物（容斥原理+DP）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1042

【题目大意】

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

【题解】

　　我们首先预处理出没有限制情况下不同容量的方案数，等价于一般的背包问题
　　之后对于硬币数量限制问题考虑容斥，
　　方案数等于无限制方案数-面值为c1的硬币超出限制的方案数-面值为c2的硬币超出限制的方案数-……
　　+面值为c1和c2的硬币同时超出限制的方案数+……
　　-……+面值为c1,c2,c3,c4的硬币同时超出限制的方案数
　　对于硬币ci，其超出限制的方案数为dp[x-c[i]*(d[i]+1)],然后容斥即可。

【代码】

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N=100010;

LL dp[N],ans;

int T,x,d[5],c[5];

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

    if(sum<0)return;

    if(x==5){

        if(k&1)ans-=dp[sum];

        else ans+=dp[sum];

        return;

    }dfs(x+1,k+1,sum-(d[x]+1)*c[x]);

    dfs(x+1,k,sum);

}

int main(){

    for(int i=1;i<=4;i++)scanf("%d",&c[i]);

    scanf("%d",&T);

    dp[0]=1;

    for(int i=1;i<=4;i++)for(int j=c[i];j<=100000;j++)dp[j]+=dp[j-c[i]];

    while(T--){

        for(int i=1;i<=4;i++)scanf("%d",&d[i]);

        scanf("%d",&x); ans=0;

        dfs(1,0,x);

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

    }return 0;

}

巴特西

BZOJ 1042：[HAOI2008]硬币购物（容斥原理+DP）

最新文章

热门文章