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