SRM694div1Easy TrySail
N <= 50, a[i] < 256の数列を、グループの数すべてのXorが最大となるようにグループ分けする問題。
貪欲で解こうとしてかなり筋の悪いことをしてしまいましたが、Xor < 256 グループ1とグループ2のxorを状態に持ってメモリ節約dpすると解けます。グループ3のxorは全部のxor ^ 1 ^ 2なので持たなくて大丈夫。
コードはcafelierさんのを参考にしました。
class TrySail { public: int get(vector<int> strength) { vector<bool> dp(65536, false); dp[0] = true; int cur = 0, nxt = 1, all = 0; for(int s : strength) { vector<bool> tmp = dp; rep(a, 256) rep(b, 256) if(dp[a * 256 + b]) tmp[(a ^ s) * 256 + b] = tmp[a * 256 + (b ^ s)] = true; dp.swap(tmp); all ^= s; } int ans = 0; rep(a, 256) rep(b, 256) if(dp[a * 256 + b]) ans = max(ans, a + b + (all ^ a ^ b)); return ans; } };
http://mio-hirona.hatenablog.com/entry/2016/05/15/184520
↑の問題の時も低難易度なのに全然わからんやばいと思ったのですがこういうDP本当に苦手ですね……。
本当に苦手。わかればなんてことないんですが。そもそもa[i] < 256に気付けよという感じ。そろそろdiv2に落ちそうです。