(luogu1373)小a和uim之大逃离

发表于 | 分类于 ，

思路:

dp

用$d(i,j,l,0/1)$表示走到第i行j列, 两人相差l, 现在由小a/uim吸收魔液的方法数.

当小a吸收魔液时, 相当于增大差距; 当uim吸收魔液时相当于减少差距.

则可以写出如下状态转移方程:

统计所有l=0的d的和即得到答案.

下面是代码实现

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
using namespace std;
const int Mn(805),MO(1000000007);
int n,m,k;
int a[Mn][Mn],d[Mn][Mn][20][2];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i(1);i<=n;++i)
        for(int j(1);j<=m;++j)
            scanf("%d",&a[i][j]);
    d[1][1][a[1][1]][0]=1;  //初始化
    int ans(0);
    for(int i(1);i<=n;++i)
    {
        for(int j(1);j<=m;++j)
        {
            if(i==1 && j==1)    continue;
            for(int l(0);l<=k;++l)
            {
                d[i][j][l][0] = (1ll*d[i-1][j][(l-a[i][j]+k+1)%(k+1)][1]+1ll*d[i][j-1][(l-a[i][j]+k+1)%(k+1)][1])%MO;
                d[i][j][l][1] = (1ll*d[i-1][j][(l+a[i][j])%(k+1)][0]+1ll*d[i][j-1][(l+a[i][j])%(k+1)][0])%MO;
            }
            ++d[i][j][a[i][j]][0]; d[i][j][a[i][j]][0] %= MO;   //加上从i,j出发的情况
            ans = (1ll*ans+1ll*d[i][j][0][1])%MO;
        }
    }
    cout << ans;
    return 0;
}