DP爬楼
problem1 一双木棋 chess
分析性质，发现每个时刻的状态都是锯齿线，考虑怎么把状态压进去，对于每个时刻都对应一个在 n 维上走了若干步和 m 维上走了若干步，如果用一个 11 进制数存的话会有 \(1e10\) 种状态，但实际上状态非常稀疏，每个锯齿都可以用一个数对 \((i,j),i\leq n,j\leq m\) 表示，所以总的状态数在 \({n+m}\choose n\) 左右，记搜可过。
点击查看代码
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;
}
key：状压状态数分析，状态描述