P1373 小a和uim之大逃离

一道比较好的dp题。

可以以任一节点为起点。以任意节点为终点。然后是转移是有方向的。

然后我们在处理初始状态时，就不能只处理一个，应该站在全局角度中思考。

然后对于所有能影响结果都都应记录

但如果记录两人分别的魔液的数量，显然空间是不够的。这道题是让我们求解相等时的情况，我们应该讲注意力放在差上

这样，不仅节约了一维，也使统计次数更叫方便

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int f[801][801][17][2];//f[i][j][k][0/1]表示在（i，j）时，差为k，谁已经行动完（1:小a  0：uim）
int map[801][801];
const int mod=1e9+7;
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    k++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            f[i][j][map[i][j]%=k][1]=1;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int l=0;l<=k;l++)
            {
                f[i][j][l][0]=(f[i][j][l][0]+f[i-1][j][(l+map[i][j]+2*k)%k][1])%mod;//枚举差，并转移
                f[i][j][l][0]=(f[i][j][l][0]+f[i][j-1][(l+map[i][j]+2*k)%k][1])%mod;
                f[i][j][l][1]=(f[i][j][l][1]+f[i-1][j][(l-map[i][j]+2*k)%k][0])%mod;
                f[i][j][l][1]=(f[i][j][l][1]+f[i][j-1][(l-map[i][j]+2*k)%k][0])%mod;
            }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)            ans=(ans+f[i][j][0][0])%mod;//这里也可以填写f[i][j][k][0]，具体为什么，可以思考思考qwq
    printf("%d",ans);
}