题解 P1373 【小a和uim之大逃离】
By lzn 动态规划或者说是递推常规题。
f[i][j][p][q]表示他们走到(i,j)，且两人魔瓶内魔液量的差为p时的方法数。q=0表示最后一步是小a走的，q=1表示最后一步是uim走的。题目中说魔瓶的容量为k，实际上就是动归时p需要对k+1取余数，即p只有0~k，k+1种可能。答案为所有f[i][j][0][1]的和。
动归方程如下：（为了方便已经令k=k+1）
f[i][j][p][0]+=f[i-1][j][(p-mapp[i][j]+k)%k][1] (i-1>=1)
f[i][j][p][0]+=f[i][j-1][(p-mapp[i][j]+k)%k][1] (j-1>=1)
f[i][j][p][1]+=f[i-1][j][(p+mapp[i][j])%k][0] (i-1>=1)
f[i][j][p][1]+=f[i][j-1][(p+mapp[i][j])%k][0] (j-1>=1)
还有每个格子都有可能作为小a的起始格子，所以初始时对于所有i、j，f[i][j][mapp[i][j]][0]=1。
算法复杂度o(n*m*k)。