(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
32
#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;
}