洛谷P1373小a和uim大逃离题解

题目

这个题好坑啊，首先是他会卡空间，然后我们就只能把一种比较好理解的状态给舍弃，因为空间开不下，然而采用一种难理解的状态就是\(dp[i][j][l][0/1]\)表示\(i\)，\(j\)位置，两者的差为\(l\)，当前由谁来吸收的方案数。

然后我们就可以推出状态转移方程，此状态转移方程很好写，主要就是状态非常难想，因此我们如果状态转移方程想不出来的话，就需要考虑换个状态。并且我们因为需要保证数组下标为正，所以差值为正的时候，因为我们需要\(mod~k\)因此就可以根据负数取模的性质，加上k就好了，还要注意一开始k++，也是一个坑点

dp[i][j][l][0] =  ((long long) dp[i - 1][j][(l - data[i][j] + k) % k][1] + dp[i][j][l][0] ) % mod;//此时该小a取了，所以

dp[i][j][l][1] =  ((long long) dp[i - 1][j][(l + data[i][j]) % k][0] + dp[i][j][l][1] ) % mod;//此时该uim取了，所以差值变小，因此l相比于l+data[i][j]来说的话，是小的。

dp[i][j][l][0] =  ((long long) dp[i][j - 1][(l - data[i][j] + k) % k][1] + dp[i][j][l][0] ) % mod;

dp[i][j][l][1] =  ((long long) dp[i][j - 1][(l + data[i][j]) % k][0] + dp[i][j][l][1] ) % mod;

巴特西

洛谷P1373小a和uim大逃离题解

题目

最新文章

热门文章