題解

我們可以先簡單的想一種狀態，也就是$dp[i][j][x][y][t]$，這是最暴力的。
當$t=0$時，表示小a處于$(i,j)$位置，其中小a擁有x魔液，uim擁有y的魔液時候的方案總數。$t=1$的時候反過來，意義類似。
這樣的話我們很容里列出轉移方程（這里就不給出了），但是這樣的話內存和時間上都會爆炸$800?800?15?15?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之大逃离 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。