洛谷P1373：小 a 和 uim 之大逃离

洛谷P1373：小 a 和 uim 之大逃离

题意

略

思路

DP：记 dp[i][j][c][0/1] 表示走到 \(i\) 行 \(j\) 列时，两人容量之差为 \(c\) 的方案数，\(0\) 表示 \(\rm 小a\) 走的最后一步，\(1\) 表示 \(\rm uim\) 走的最后一步。

容易得出转移方程：

dp[i][j][l][0]+=dp[i-1][j][l-a[i][j]+k][1];
dp[i][j][l][0]+=dp[i][j-1][l-a[i][j]+k][1];
dp[i][j][l][1]+=dp[i-1][j][l+a[i][j]+k][0];
dp[i][j][l][1]+=dp[i][j-1][l+a[i][j]+k][0];

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int dp[805][805][20][2];
int a[805][805];
const int mod=1e9+7;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    k++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j],dp[i][j][a[i][j]%k][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int l=0;l<=k;l++)
            {
                dp[i][j][l][0]+=dp[i-1][j][(l-a[i][j]+k)%k][1];
                dp[i][j][l][0]+=dp[i][j-1][(l-a[i][j]+k)%k][1];
                dp[i][j][l][1]+=dp[i-1][j][(l+a[i][j]+k)%k][0];
                dp[i][j][l][1]+=dp[i][j-1][(l+a[i][j]+k)%k][0];
                dp[i][j][l][0]%=mod;
                dp[i][j][l][1]%=mod;
            }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans+=dp[i][j][0][1],ans%=mod;
    cout<<ans;
    return 0;
}