SRM556 Div1 Easy - XorTravelingSalesman
問題
n個の町があり、i番目の町の価値はa[i]である
最初は町0にいてスコアはa[0]
スコアがpの状態で町iに移動するとスコアはp xor a[i]に変化する
好きな町で終了できるときスコアの最大値を求めよ
1 <= n <= 50
0 <= a[i] <= 1023
解法
d[i][j]: 町iにスコアjでたどり着けるかどうか
というboolのテーブルを再帰で埋めるだけ
class XorTravelingSalesman { public: int n, res = 0; bool d[55][1<<10] = {}; vector<int> a; vector<string> e; void rec(int v, int x) { chmax(res, x); d[v][x] = 1; rep(i,n) if (e[v][i]=='Y' && !d[i][x^a[i]]) rec(i,x^a[i]); } int maxProfit(vector<int> a_, vector<string> e_) { a = a_, e = e_, n = a.size(); rec(0,a[0]); return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12175&rd=15178