洛谷P1373 小a和uim之大逃离 动态规划

题解

我们可以先简单的想一种状态，也就是$dp[i][j][x][y][t]$，这是最暴力的。
当$t=0$时，表示小a处于$(i,j)$位置，其中小a拥有x魔液，uim拥有y的魔液时候的方案总数。$t=1$的时候反过来，意义类似。
这样的话我们很容里列出转移方程（这里就不给出了），但是这样的话内存和时间上都会爆炸$800\ast 800\ast 15\ast 15\ast 2=288000000$，因此我们必须对状态进行压缩。
从要求出发，题目中要求两者魔力相等的方案数，也就是差值为$0$的方案数。
我们定义 $dp[i][j][x][t]$。当t = 0时候，表示小a位于(i,j)位置，且小a的魔力与uim的魔力相差为x的方案数。
容易列出状态转移方程：
$dp[i][j][x][t]=dp[i][j-1][p][1-t]+dp[i-1][j][p][1-t]$
其中$p=(mat[i][j]-t+k)\%k$
推导过程：
$su{m}_t+mat[i][j]-su{m}_{1-t}=x$
$p=su{m}_{1-t}-su{m}_t=mat[i][j]-x=(mat[i][j]-x+k)\%k$

额外条件要注意！
由于只能从小a开始，因此初始化只初始化$t=0$的情况
由于只能从uim结束，因此答案只加$dp[i][j][0][1]$

---

代码

#include <iostream> #include <cstdio> using namespace std; int n,m,k; int dp[801][801][20][2]; const int mod = 1e9+7; int mat[801][801]; int main(){scanf("%d%d%d",&n,&m,&k);++k;for(int i = 1;i <= n;++i){for(int j = 1;j <= m;++j){scanf("%d",&mat[i][j]);dp[i][j][mat[i][j]%k][0] = 1;}}long long ans = 0;for(int i = 1;i <= n;++i){for(int j = 1;j <= m;++j){for(int t = 0;t < k;++t){int p = (mat[i][j]-t+k)%k;dp[i][j][t][0] += (dp[i-1][j][p][1]+dp[i][j-1][p][1])%mod;//p = (mat[i][j]+t)%k;dp[i][j][t][1] += (dp[i-1][j][p][0]+dp[i][j-1][p][0])%mod;dp[i][j][t][0] %= mod;dp[i][j][t][1] %= mod;//printf("i:%d,j:%d,t:%d,val:%d\n",i,j,t,dp[i][j][t][1]);}ans = (ans + dp[i][j][0][1])%mod;}}cout<<ans<<endl; }

总结

以上是生活随笔为你收集整理的洛谷P1373 小a和uim之大逃离 动态规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。