BZOJ1042[HAOI2008]硬币购物（容斥定理+完全背包)

本文主要是介绍BZOJ1042[HAOI2008]硬币购物（容斥定理+完全背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

输入格式
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

输出格式
每次的方法数

输入输出样例
输入 #1复制
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
输出 #1复制
4
27
说明/提示
di,s<=100000

tot<=1000

[HAOI2008]

思路：
作tot次多重背包肯定会超时
考虑没有硬币数量限制的情况，那就是完全背包，答案就是dp[s]。
再考虑有限制的情况，假设只有一种硬币，只有d个。
先使得ans = dp[s]，其中包含了不合理情况。
那么花d+1个，d+2个，d+3个…d+n个的情况都是不合理的。如何减去这些不合理情况呢？
dp[s]意味着容量为s的时候的完全背包方案数，子状态为dp[s - x*c]。而dp[s - (d+1)*c]则代表了所有花超过d个硬币的子状态（因为dp[s - (d+1)*c]也要从其他状态花硬币转移上来，类似前缀和，包含了之前的所有情况）。

回到题目，题目有4种硬币，此时就可以用容斥写。总体数目减去一个不合理的加上两个不合理的减去三个不合理的加上四个不合理的。

玄学。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
ll dp[100005];
int c[5],d[5],tot,sum;void DP()
{dp[0] = 1;for(int i = 1;i <= 4;i++){for(int j = c[i];j <= 100005;j++){dp[j] += dp[j - c[i]];}}
}ll f(int x)
{return 1ll * (d[x] + 1) * c[x];
}int main()
{scanf("%d %d %d %d %d",&c[1],&c[2],&c[3],&c[4],&tot);DP();while(tot--){scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&sum);ll ans = dp[sum];if(sum >= f(1))ans -= dp[sum - f(1)];if(sum >= f(2))ans -= dp[sum - f(2)];if(sum >= f(3))ans -= dp[sum - f(3)];if(sum >= f(4))ans -= dp[sum - f(4)];if(sum >= f(1) + f(2))ans += dp[sum - f(1) - f(2)];if(sum >= f(1) + f(3))ans += dp[sum - f(1) - f(3)];if(sum >= f(1) + f(4))ans += dp[sum - f(1) - f(4)];if(sum >= f(2) + f(3))ans += dp[sum - f(2) - f(3)];if(sum >= f(2) + f(4))ans += dp[sum - f(2) - f(4)];if(sum >= f(3) + f(4))ans += dp[sum - f(3) - f(4)];if(sum >= f(1) + f(2) + f(3))ans -= dp[sum - f(1) - f(2) - f(3)];if(sum >= f(1) + f(3) + f(4))ans -= dp[sum - f(1) - f(3) - f(4)];if(sum >= f(1) + f(2) + f(4))ans -= dp[sum - f(1) - f(2) - f(4)];if(sum >= f(2) + f(3) + f(4))ans -= dp[sum - f(2) - f(3) - f(4)];if(sum >= f(1) + f(2) + f(3) + f(4))ans += dp[sum - f(1) - f(2) - f(3) - f(4)];printf("%lld\n",ans);}return 0;
}

改写成dfs

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
ll dp[100005];
int c[5],d[5],tot,sum;void DP()
{dp[0] = 1;for(int i = 1;i <= 4;i++){for(int j = c[i];j <= 100005;j++){dp[j] += dp[j - c[i]];}}
}ll f(int x)
{return 1ll * (d[x] + 1) * c[x];
}ll ans;void dfs(int cnt,ll s,int sign)
{if(cnt == 5){ans += dp[s] * sign;return ;}if(s >= f(cnt))dfs(cnt + 1,s - f(cnt),-sign);dfs(cnt + 1,s,sign);
}int main()
{scanf("%d %d %d %d %d",&c[1],&c[2],&c[3],&c[4],&tot);DP();while(tot--){scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&sum);ans = 0;dfs(1,sum,1);printf("%lld\n",ans);}return 0;
}