51nod 1053

题解

动态规划

$f[a][b][c][d]$ 表示从 $(1, 1)$ 走到 $(a, b)$ 和从 $(n, m)$ 走到 $(c, d)$ 的方案数

$f[a][b][c][d]$
$= f[a][b - 1][c][d + 1] + f[a][b - 1][c + 1][d] + f[a - 1][b][c + 1][d] + f[a - 1][b][c][d + 1]$

当然这里忽略了判断条件
时空爆炸

考虑如果知道的 $s = a + b, a, c$ 就可以推出 $d$
因此可以压掉一维，时间复杂度 $n ^ 3$

然而空间依旧爆炸

发现 $f[s][*][*]$ 只与 $f[s - 1][*][*]$ 有关
因此只开两个即可

抽离

f[cur][x1][x2] = (f[cur][x1][x2] + f[cur ^ 1][x1][x2] + f[cur ^ 1][x1 - 1][x2] + f[cur ^ 1][x1][x2 + 1] + f[cur ^ 1][x1 - 1][x2 + 1]) % Mod;

最后 $Ans = \sum_{i = 1}^{n}f[cur][i][i]$

如果 $n + m$ 为奇数
$Ans += \sum_{i = 1}^{n} f[cur][i][i + 1]$