自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:24:21，当前版本为作者最后更新于2013-07-14 19:01:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)。