本文主要是介绍CCPC 2018 秦皇岛 I题 Riddle 状态压缩DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Sample Input
3
3
1 1 1
5
1 1 2 2 3
10
1 2 3 4 5 6 7 8 9 10
Sample Output
7
15
127
题意：
T组测试样例，每一组输入n，然后输入n个数据，每一个数据只有两个含义：
1.代表1个物品重量
2.代表一个礼品包的种量，礼品包的满足是任意个其他物品加和
注意包可以放在另一个包里。
题意可能有点难懂
举一个例子：
5
1 1 2 2 3
、
分析：
思路：状压DP
我们设两种状态：
1. 物品选入状态： 0代表表示背包，1代表表示选入其为物品
2. 背包选入状态： 1代表表示选入背包，0代表不选入背包，比如，11101表示物品1，3，4，5合并成一个背包，我们用f[11101]表示该种合并背包的方案数（eg：1 1 2合并就有两种）。
最后枚举物品选入状态i和背包选入状态j，如果i&j==0 表示i中有物品被背包选入，肯定是不行的。
状态转移
Dp[i|j]+=dp[j]*f[i]
i|j表示这两个状态可以合并成一个状态，实现了背包嵌套问题
也就是说，只要实现了选取0和1个背包就能构造出来选2……n个背包的情况。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int dp[N],sum[N],f[N];int a[20];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=0;i<(1<<n);i++){dp[i]=1;sum[i]=f[i]=0;}for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++) //枚举物品{for(int j=1;j<(1<<n);j++){//枚举背包状态if(j&(1<<(i-1))) //每一个状态下j，物品的总质量sum[j]+=a[i];}}for(int i=1;i<=n;i++){for(int j=1;j<(1<<n);j++){if(j&(1<<(i-1))){ //选取第i个物品为背包的情况下，f[j]的方案数if(sum[j]-a[i]==a[i])f[j]++;}}}for(int i=1;i<(1<<n);i++)//枚举背包状态{int k=(1<<n)-1-i; for(int j=k;;j=(j-1)&k){//枚举与背包状态相斥的物品状态：eg：背包111110，物品：000001dp[i|j]+=dp[j]*f[i]; //具体原理机制待补if(j==0)break;}}printf("%d\n",dp[(1<<n)-1]);}return 0;
}
这篇关于CCPC 2018 秦皇岛 I题 Riddle 状态压缩DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
