这题对于我来说是真的难。。。

题目大意：言简意赅。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<
    
     >a[i];        sum1[i]=a[i];    }    for(int i=0;i