洛谷题单指南-状态压缩动态规划-P1450 [HAOI2008] 硬币购物
原题链接：https://www.luogu.com.cn/problem/P1450
题意解读：4种硬币，每种硬币币值c[i]有d[i]个，求用硬币凑出总价值s的方案数。
解题思路：
第一直觉是多重背包，但是看一下数据范围，就直接劝退了。
问题的关键是每种硬币都有数量限制，一个个枚举太耗时。
转换一下思维，假设硬币没有数量限制呢？
设f[s]为总价值是s的方案数，直接用完全背包优化方案可以在4*n复杂度求解，得到s以内所有价值的方案数。
由于没有数量限制，f[s]里方案，有合法的，也有不合法的，什么样的是不合法呢？
显然，总价值没有超，那不合法只可能是数量超了，一共有四种可能：硬币1数量超了，硬币2数量超了，硬币3数量超了，硬币4数量超了。
如何表示硬币数数量超了？
比如，如果硬币1数量超了，那么f[s - c[1] (d[1] + 1)]的方案数里一定包含硬币1数量超了的部分，以此类推，f[s - c[i] (d[i] + 1)]的方案数里一定包含硬币i数量超了的部分。
但是，f[s - c[1] (d[1] + 1)] + f[s - c[2] (d[2] + 1)] + f[s - c[3] (d[3] + 1)] + f[s - c[4] (d[4] + 1)] 是否表示所有不合法的方案数呢？答案是否定的！因为，同一个方案，如果硬币1和硬币2都超了，f[s - c[1] (d[1] + 1)] 和f[s - c[2] (d[2] + 1)] 就重复计数了，要排除掉，就要减去硬币1和硬币2都超的情况，计算方式为f[s - c[1] (d[1] + 1) - c[2] (d[2] + 1)]，其他的两种硬币都超的组合同理可得。
进一步，前面的计算，对于三种硬币同时超了的情况会重复扣减，要加回来，计算方式为f[s-三种硬币超了的情况]。
最后，四种硬盘同时超了的情况重复计数，要减去。
以上的分析，不就是容斥原理！
我们设A1，A2，A3，A4表示硬币1,2,3,4超了的方案，|A1|,|A2|,|A3|,|A4|表示四种硬币各自超了的方案数，最终要求解的是：
f[s] - |A1 U A2 U A3 U A4| = f[s] - (|A1| + |A2| + |A3| + |A4| - |A1∩A2| - |A1∩A2| - … + |A1∩A2∩A3| + |A1∩A2∩A4| + … - |A1∩A2∩A3∩A4|)
容斥原理的展开可以借助于枚举子集，用0 ~ 15的二进制表示状态，如1010表示|A1∩A3|，有偶数个1，应该是减法。
100分代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
LL f[N]; //f[i]表示凑出价值i的方案数
int c[5], d[5];
int t, s;
int main()
{
for(int i = 1; i <= 4; i++) cin >> c[i];
//执行完全背包计算f
f[0] = 1;
for(int i = 1; i <= 4; i++)
{
for(int j = c[i]; j <= N; j++)
{
f[j] += f[j - c[i]];
}
}
cin >> t;
while(t--)
{
for(int i = 1; i <= 4; i++) cin >> d[i];
cin >> s;
LL ans = f[s];
//枚举子集实现容斥原理
for(int i = 1; i < 16; i++)
{
LL tmp = 0;
int cnt = 0;
for(int j = 1; j <= 4; j++)
{
if(i >> j - 1 & 1)
{
cnt++;
tmp += 1ll * c[j] * (d[j] + 1);
}
}
if(s - tmp < 0) continue;
if(cnt % 2 == 0) ans += f[s - tmp];
else ans -= f[s - tmp];
}
cout << ans << endl;
}
}