SRM556 Div2 Medium "XorTravelingSalesman"
問題
頂点に値がある双方向に移動できるグラフが与えられる。
現在のポイントをPとし、値Vの頂点に移動した時、
ポイントはP XOR Vになる。
例)
ポイントが5のときに値3の頂点に移動すると、
ポイントが6になる。
5(0101) XOR 3(0011) = 6(0110)
移動回数に制限はない。
また好きな時にやめる事ができ、
そのときもっていたポイントが結果となる。
最大のポイントを求めよ。
制約
1 <= 頂点の数 <= 50
0 <= 頂点の値 <= 1023
考えた事
どう手をつけていいのかわからん・・・・
とりあえず、遇数回通った頂点は反映されず、
奇数回通った頂点の値だけXORしてくわけだ
偶数回奇数回って完全にコントロールできそう?
うん。きっとできる!(直感)
ってことは、最大になるよう好きな頂点を選べるな
総当りだと2^50か・・・DP?
DPの式の立て方分からん・・・(時間切れ)
i番目の頂点までで、0~1023(0000000~1111111)を作れるか否かでいける!
Failed System Test
あ、頂点0から辿り着けない頂点抜かさなきゃ
DPって自力で式立てられた時は気持ちいいな~
ソースコード
const int MAX_N = 50; const int MAX_V = 1023; int N; bool dp[MAX_N+1][MAX_V+1]; // dp[i][p] 頂点をi個使った時にポイントpはできる? bool reach[MAX_N]; // インデックスiの頂点に頂点0から辿り着けるか class XorTravelingSalesman { public: int maxProfit(vector <int> cityValues, vector <string> roads){ // dpを初期化 memset( dp, false, sizeof(dp) ); dp[0][0] = true; // 頂点1個も使わない時はポイントは0 // reachを初期化 N = roads.size(); memset( reach, false, sizeof(reach) ); queue<int> que; que.push(0); while( !que.empty() ){ int v = que.front(); que.pop(); reach[v] = true; for( int i = 0; i < N; i++ ){ if( roads[v][i] == 'Y' && !reach[i] ) que.push(i); } } // dpを埋めてく for( int i = 1; i <= N; i++ ){ for( int v = 0; v <= MAX_V; v++ ){ if( reach[i-1] ){ dp[i][v] = dp[i-1][v] || dp[i-1][v^cityValues[i-1]]; }else{ dp[i][v] = dp[i-1][v]; } } } // できるポイントで一番大きいのを取得 int res = 0; for( int v = MAX_V; v >= 0; v-- ){ if( dp[N][v] ){ res = v; break; } } return res; } }