题意
题目描述
有 n 个人打算分成 n 个小组，对于这 n 个人的任意一个组合，都有一个被称为“和谐度”的东西。现在，他们想知道，如何分组可以使和谐度总和最大。每个人必须属于某个分组，可以一个人一组。
输入格式
第 行为 ，表示有 个人。
接下来2n-1行，按照 进制给出每个分组的和谐度。（比如接下来第 5 行，也就是总共第 6 行，2 进制为00000101 ，则表示第 1 个人和第 3 个人这个分组的和谐度，第 31 行则为 1~5 在一起的和谐度）输出格式
一行一个整数，为最大和谐度和。
样例
输入样例
3 41 12 57 94 89 23 12输出样例
151数据范围与提示
对于 100% 数据，满足1<=n<=16 ，1<=每个组的和谐度<=1e6，输入均为整数。
解析
对于本题，很容易的想到dp[i]表示i状态的最大和谐度，最终答案为dp[(1<<n)-1]，但如果只是暴力（枚举所有状态，判断是否是当前状态的子集）是不行的，复杂度为O(4n)会超时
但如果能够直接枚举当前状态的所有子集（子集枚举），根据二项式定理可得（我也不知道怎么得出来的），复杂度就降到了O(3n)
那么如何进行？
设 i 为当前状态,for(int j=i;j>0;j=(j-1)&i)，枚举出来的j就是所有子集
正确性说明：
j 从 i 开始从大到小每次-1，而且&运算之后一定不会更大，所以 j 在循环里单调不上升
每次-1之后最低位的1会变成0，更低位会产生新的1，新的1会被&运算删掉，这样就枚举出一个子集
此后 j 一直变小，相当于高位的1慢慢向低位移动
例如：枚举101010的子集
| 1 | 101000 |
| 2 | 100010 |
| 3 | 100000 |
| 4 | 001010 |
| 5 | 001000 |
| 6 | 000010 |
| 7 | 000000 |
tips：i^j在 j 是 i 的子集是和i-j等效
30opt暴力代码
这里实际上枚举的是当前状态和可以继续叠加的状态，并不是枚举子集再判断，但是本质一样
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
int n,a[1<<16];
ll dp[1<<16];
int main()
{
scanf("%d",&n);
for(int i=1;i<(1<<n);i++)
scanf("%d",&a[i]);
for(int i=0;i<(1<<n);i++)
for(int j=0;j<(1<<n);j++)
{
if(i&j) continue;
dp[i|j]=max(dp[i|j],dp[i]+dp[j]);
}
printf("%lld",dp[(1<<n)-1]);
return 0;
}100pts代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
int n,a[1<<16];
ll dp[1<<16];
int main()
{
scanf("%d",&n);
for(int i=1;i<(1<<n);i++)
scanf("%d",&a[i]),dp[i]=a[i];
/*
for(int i=0;i<(1<<n);i++)
for(int j=0;j<(1<<n);j++)
{
if(i&j) continue;
dp[i|j]=max(dp[i|j],dp[i]+a[j]);
}
*/
for(int i=0;i<(1<<n);i++)//枚举目标状态
for(int j=i;j>0;j=(j-1)&i)//枚举目标状态子集
{
dp[i]=max(dp[i],dp[j]+dp[i^j]);
}
printf("%lld",dp[(1<<n)-1]);
return 0;
}