結果

問題 No.698 ペアでチームを作ろう
ユーザー 2nanoda series
提出日時 2023-03-11 11:46:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 1,000 ms
コード長 2,526 bytes
コンパイル時間 663 ms
コンパイル使用メモリ 70,412 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-18 06:17:12
合計ジャッジ時間 1,349 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>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<int> dp(1<<n,0);
    // for(int i=0;i<(1<<n);i++){
    //     for(int j=0;j<n;j++){
    //         if ((i&(1<<j))==(1<<j)) continue;// ｊはiに入ってはいけない
    //         for(int k=0;k<n;k++){
    //             if ((i&(1<<k))==(1<<k)) continue;// kはiに入ってはいけない
    //             if (j==k) continue ; // ペアは異なるもので組む必要がある．
    //             int new_i=i | ((1<<j)|(1<<k));
    //             dp[new_i] = max(dp[i]+(a[j] ^ a[k]) ,dp[new_i] );
    //         }
    //     }
    // }

    
    for(int j=n-1;j>=0;j--){
        for(int k=0;k<n;k++){
            for(int i=(1<<n)-1;i>=0;i--){
                if ((i&(1<<j))==(1<<j)) continue;// ｊはiに入ってはいけない
                if ((i&(1<<k))==(1<<k)) continue;// kはiに入ってはいけない
                if (j==k) continue ; // ペアは異なるもので組む必要がある．
                int new_i=i | ((1<<j)|(1<<k));
                dp[new_i] = max(dp[i]+(a[j] ^ a[k]) ,dp[new_i] );
            }
        }
    }

    // debug
    // for(int i=0;i<(1<<n);i++){
    //     cout<<dp[i]<<" ";
    // }

    cout << dp[(1<<n)-1]<<endl;
    return 0;
}
0