这题对于我来说是真的难。。。
题目大意：言简意赅。2的N次方个数，存为Ai，令1≤K≤2的N次方−1，请你求出(i,j)，使Ai+Aj最大，并且0<=i< j<=2的N次方-1且(i or j)≤K。输出Ai+Aj的最大值。
思路：这一题长得是真的不像DP。
这道题虽然言简意赅，但大部分都是为了严谨，我们最要注意的就是i|j<=k这句话。用膝盖想一下便知若i|j<=k，则i|j必定<=k+1。那么我们就可以设dp[k]为k下Ai+Aj的最大值，那么就有dp[k]=max(dp[k-1],不知道什么东西)。我们主要要思考的就是这个“不知道什么东西”。
那么这个“不知道什么东西”肯定是区别于k-1下的那些(i,j)的，也就是说是新的几对(i,j)，根据样例或者自己证明等等方式可知若x|y=z，那么x和y都必定小于等于z。
口胡证明： 因为或运算在都是0的情况下才会是0，不可能把1变成0，只会把0变成1，所以数字只会变大不会变小
接上文思路：那么，也就是说新的这几对(i,j)里，i或j等于k（因为小于等于k的前面都有了嘛），因为不管顺序，我们就直接让i等于k。式子就变成了k|j=k，根据证明可知j小于等于k，我们可以通过更改1的位数为0来得到所有小于k的数。但在这里我选择了反过来思考：我们循环这几位和k，然后更改k中的这一位的1为0，得到小于k的j，运用两个数组更新与这时的k相对应的j的最大值就行了，我们得到的就是两个一一对应的数组，每一个k对应其最大的j。
我不怎么会写dp方程，大概就是dp[k]=max(dp[k-1],a[k]+maxa[j])
（萌新瑟瑟发抖）
AC程序
//库省略
using namespace std;
const int maxn=300005;
int n,a[maxn];
int sum1[maxn],sum2[maxn];
int ans[maxn];
void upday(int val,int pos)
{
if(val>sum1[pos])
{
sum2[pos]=sum1[pos];
sum1[pos]=val;
}
else
{
if(val>sum2[pos])
{
sum2[pos]=val;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<(1<<n);i++)
{
cin>>a[i];
sum1[i]=a[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<(1<<n);j++)
{
int t=1<<i;
if(!(j&t))
{
int nowp=(j|t);
int old=sum1[j];
upday(old,nowp);
old=sum2[j];
upday(old,nowp);
}
}
}
for(int i=0;i<(1<<n);i++)
{
if(i!=0)
ans[i]=max(ans[i-1],sum1[i]+sum2[i]);
else
ans[i]=sum1[i]+sum2[i];
}
for(int i=1;i<(1<<n);i++)
{
cout<<ans[i]<<endl;
}
return 0;
}