时间限制: 2 Sec 内存限制: 128 MB
题目描述
Kiana wants to give you a riddle. She gives you a piece of paper with n numbers on it. Any two numbers are considered different although they may have the same value.
Some numbers on the paper represent the weight of some toys, while the others represent the weight of some giftbags containing those toys. It is NOT required that each toy should be put into a giftbag, but each giftbag whose weight written on the paper should contain at least one toy. The weight of a giftbag is the total weight of toys it contains. Two toys or two giftbags are considered different if their weights are represented by different numbers.
The riddle is how many different ways Kiana can get these numbers on the paper. Two ways are considered different if one of the numbers represents different kinds of weight (In one way it represents the weight of a toy but in the other way it represents the weight of a giftbag) or one of the giftbags contains different toys.
输入
Read from the standard input.
There are several test cases in the data. The first line contains one integer T(T ≤ 5), the number of cases. Then for each test case:
The first line contains one integer n denoting how many numbers are written on the paper. It is guaranteed that n is no more than 15.
The second line contains n integers, which represent the numbers Kiana writes on the paper. It is guaranteed that each of the numbers is no more than 2000.
输出
Write to the standard output.
For each test case, output one integer denoting how many different ways Kiana can get these numbers.
样例输入
3
3
1 1 1
5
1 1 2 2 3
10
1 2 3 4 5 6 7 8 9 10
样例输出
7
15
127
提示
In the first test case, there are 7 different ways to get these numbers:
1.All three numbers represent the weight of toys, which means there are no giftbags.
2.The first number represents the weight of a giftbag containing a toy whose weight is represented by the second number. The third number represents the weight of a toy not in a giftbag.
3.The first number represents the weight of a giftbag containing a toy whose weight is represented by the third number. The second number represents the weight of a toy not in a giftbag.
4.The second number represents the weight of a giftbag containing a toy whose weight is represented by the first number. The third number represents the weight of a toy not in a giftbag.
5.The second number represents the weight of a giftbag containing a toy whose weight is represented by the third number. The first number represents the weight of a toy not in a giftbag.
6.The third number represents the weight of a giftbag containing a toy whose weight is represented by the first number. The second number represents the weight of a toy not in a giftbag.
7.The third number represents the weight of a giftbag containing a toy whose weight is represented by the second number. The first number represents the weight of a toy not in a giftbag.
Notice that 2. and 3. are different ways although they both mean one giftbag containing only one toy with weight 1. But the toy in the giftbag in two ways are considered to be different because their weights are represented by different numbers.
状压DP
对所有的东西进行分组，状态压缩，比方说3个物品，101(2)表示这一组中是第一个和第三个，资一个组表示的是，其中一个是包，其他都是的是这个包里面的玩具。sum数组存的就是这个组所有物品的权值的总值，然后对于一个组j，如果有一个物品a[i]的权值，满足sum[j]-a[i]==a[i]，说明对于这一个组，第i个物品可以当包，然后其他的物品当玩具放在这个包里，那么，对于每个组，就会有几个不同的物品当包，用bag数组来表示对于i状态这个组，有几种情况来对应。
最后就是转移，对于状态组i，之前的状态j一定要有(i&j==0)，因为一个物品不可能既在a组又在b组，然后对于符合条件的i，j两种状态，转移方程为dp[i|j]+=dp[j]*bag[i]，即把两个状态和起来，然后把之前的情况和这个组的可能情况乘起来就是i，j合并后的，对于所有的i|j的所有可能和起来就行
在最后一步转移的过程中，对于组i，怎么快速找到对应所有的j是个问题，如果全部遍历一遍的话，复杂度是o((1<<15)*(1<<!5))，会T掉，在这里用为运算取了个巧，对于i，只需要j=(1<<n)-1-i开始，每次更改成j=(j-1)&((1<<n)-1-i),试过8位这样是密集的，但更高位没法证明。
#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 20;
int dp[1<<16],sum[1<<16],bag[1<<16],a[maxn];
int main()
{
ios::sync_with_stdio("false");
int _;
cin>>_;
while(_--){
int n;
cin>>n;
//cout<<n<<endl;
for(int i=0;i<=(1<<n);i++){
//cout<<i<<endl;
dp[i]=1;
sum[i]=0;
bag[i]=0;
}
//cout<<"input"<<endl;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
//cout<<"start"<<endl;
for(int i=1;i<(1<<n);i++)
for(int j=1;j<=n;j++)
if(i&(1<<(j-1)))
sum[i]+=a[j];
//cout<<'a'<<endl;
for(int i=1;i<(1<<n);i++)
for(int j=1;j<=n;j++)
if(i&(1<<(j-1)))
if(sum[i]-a[j]==a[j])
bag[i]++;
//cout<<'b'<<endl;
for(int i=1;i<(1<<n);i++)
for(int j=((1<<n)-1-i);;j=(j-1)&((1<<n)-1-i)){
dp[i|j]+=dp[j]*bag[i];
if(j==0) break;
}
cout<<dp[(1<<n)-1]<<endl;
}
return 0;
}
Moriarty Yang 