problem1 一双木棋 chess
分析性质，发现每个时刻的状态都是锯齿线，考虑怎么把状态压进去，对于每个时刻都对应一个在 n 维上走了若干步和 m 维上走了若干步，如果用一个 11 进制数存的话会有 \(1e10\) 种状态，但是实际上由于落子的限制状态很稀疏可以直接 map 水过。
点击查看代码
int dfs(int x, int w){// 0 A, 1 B
if(x == ed) return 0;
if(ans[x]) return ans[x];
int sum = w ? inf : -inf, tmp = x, c[12];
c[0] = inf;
for(int i = 1; i <= n; i++) c[i] = tmp % 11, tmp /= 11;
for(int i = 1, pos = 1; i <= n; i++, pos *= 11)
if(w and c[i] < min(c[i-1], m))
sum = min(sum, dfs(x + pos, w ^ 1) - b[i][c[i]+1]);
else if(!w and c[i] < min(c[i-1], m))
sum = max(sum, dfs(x + pos, w ^ 1) + a[i][c[i]+1]);
return ans[x] = sum;
}