いい問題だった。
解法
dp[ i+1 ][ j ][ k ] := i 番目までみたとき、二組の和がそれぞれ j, k のときの残りの一組の値のとりうる最大値
として解いた。
これなら、以下に示す xor 特有の構造に気づかなくても解ける。
でも、三組の xor 和をそれぞれ a, b, c とし、
n 個全部の整数の xor を sum としたとき、
a ^ b ^ c = sum
なので、
(a ^ b) ^ a ^ b ^ c = (a ^ b) ^ sum
⇔ c = a ^ b ^ sum
なのであった。
このことを利用すればもっと簡明に解ける。
コード
#include <iostream> #include <sstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime> #include <cstring> #include <string> #include <vector> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <numeric> #include <utility> #include <iomanip> #include <algorithm> #include <functional> using namespace std; int dp[2][300][300]; class TrySail { public: int get(vector <int> str) { int n = str.size(); int res = 0; for (int i = 0; i < 2; ++i) for (int j = 0; j < 300; ++j) for (int k = 0; k < 300; ++k) dp[i][j][k] = -1; dp[0][0][0] = 0; for (int i = 0; i < str.size(); ++i) { for (int j = 0; j < 256; ++j) for (int k = 0; k < 256; ++k) { int cur = dp[i%2][j][k]; chmax(dp[(i+1)%2][j][k], cur^str[i]); chmax(dp[(i+1)%2][j^str[i]][k], cur); chmax(dp[(i+1)%2][j][k^str[i]], cur); } for (int j = 0; j < 256; ++j) for (int k = 0; k < 256; ++k) { dp[i%2][j][k] = -1; } } for (int j = 0; j < 300; ++j) for (int k = 0; k < 300; ++k) { if (dp[n%2][j][k] != -1) { chmax(res, j + k + dp[n%2][j][k]); } } return res; } };