#include #include using namespace std; int main(){ int n; cin>>n; vector a(n); for(int i=0;i>a[i]; } /* BをAの順列とする. Sum b[2*i] xor b[2*i+1] の最大値を求めよ] ただし nは2以上14以下の偶数 1<= ai <= 10^7 // 解法1 全列挙 この時,14! / ((2!)^7 * 7 !)より,14*13*12*11*10*9*8 / 2^7 = 7*13*3*11*5*9 = 10^6 だから全通り試せる. // 解法2 bit DP(動的計画法の状態をBitで表現する) すでにペアとなったものを1とし,ペアとなっていないものを0と表すとする.そのようにbitで状態iを表す. dp[i]を,状態iにおける最大値とする. この時ある状態iに対して,j,kで新たにペアを作るならば, new_i=i | (j|k); dp[new_i] = max(dp[i]+(j xor k) ,dp[new_i] ); // 更新するかしないか となる. ここで,この漸化式について,iを全体で徐々に大きくしながらその中でj,kを試すことにより, new_iはiより必ず 計算量は全状態 2^14において,全てのj,k(14)試すので 2^14*14*14=10^3*4*256=10^6である. */ vector dp(1<=0;i--){ for(int j=n-1;j>=0;j--){ for(int k=0;k