結果
問題 | No.698 ペアでチームを作ろう |
ユーザー | 2nanoda series |
提出日時 | 2023-03-11 11:46:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,944 KB |
testcase_05 | AC | 7 ms
6,944 KB |
testcase_06 | AC | 7 ms
6,944 KB |
testcase_07 | AC | 7 ms
6,944 KB |
testcase_08 | AC | 7 ms
6,940 KB |
testcase_09 | AC | 7 ms
6,940 KB |
testcase_10 | AC | 7 ms
6,940 KB |
testcase_11 | AC | 7 ms
6,944 KB |
testcase_12 | AC | 7 ms
6,944 KB |
testcase_13 | AC | 7 ms
6,944 KB |
testcase_14 | AC | 7 ms
6,940 KB |
ソースコード
#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;// jは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;// jは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; }