CodeForces - 1247E Rock Is Push【线性DP】

- 日理万妓 2023-06-15 11:03 53阅读 0赞

题目链接：[https://codeforces.com/problemset/problem/1247/E][https_codeforces.com_problemset_problem_1247_E]

题意：一个n\*m的矩阵，有个别位置会有小球，小球受到撞击会沿着方向撞到墙为止（每个小球会占一个格子）。你从左上角出发，只能向右或者向下走，问你走到右下角的方案数。

思路：首先我们定义我们的状态f\[i\]\[j\]\[0\] 表示在(i, j) 这个位置向右走的方案数，f\[i\]\[j\]\[1\] 表示在(i, j) 这个位置向下走的方案数。

先考虑向右走，如果s\[i\]\[j\] == '.' 的话，f\[i\]\[j\]\[0\] = f\[i\]\[j - 1\]\[0\] + f\[i\]\[j - 1\]\[1\] 而如果s\[i\]\[j\] == 'R' 的话（假设现在就这一个球），那么实际上是到达不了(i, m) 这个位置的，但是由于我们的状态没有考虑当前有球的情况，所以我们需要减去f\[i\]\[m\]\[1\]（1是因为存在经过（i，m）向下走的方案），具体的球数我们可以预处理算出来，向下走同理。

但是我们正常从左上推导到右下是不行的，因为在减去的时侯的状态方案数我们还没有计算出来，所以我们就倒着推导计算是一样的。

目标状态：f\[n\]\[m\]\[0\] + f\[n\]\[m\]\[1\]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn= 2e3 + 10;
    const int mod = 1e9 + 7;
    char s[maxn][maxn];
    ll f[maxn][maxn][2], d[maxn][maxn][2]; //0表示向右走，1表示向下走
    
    int main()
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
        if(s[n][m] == 'R') printf("0\n");
        else if(n == 1 && m == 1) printf("1\n");
        else
        {
            for(int i = n; i >= 1; --i) //统计行列石头数
            {
                for(int j = m; j >= 1; --j)
                {
                    d[i][j][0] = d[i][j + 1][0] + (s[i][j] == 'R'); //行
                    d[i][j][1] = d[i + 1][j][1] + (s[i][j] == 'R'); //列
                }
            }
            for(int i = 1; i < n; ++i) if(!d[i][m][1]) f[i][m][1] = 1;
            for(int i = 1; i < m; ++i) if(!d[n][i][0]) f[n][i][0] = 1;
            for(int i = n - 1; i > 0; --i)
            {
                for(int j = m - 1; j > 0; --j)
                {
                    f[i][j][0] = (f[i][j + 1][0] + f[i][j + 1][1]) % mod;
                    if(s[i][j + 1] == 'R') f[i][j][0] = (f[i][j][0] - f[i][m - d[i][j + 1][0] + 1][1] + mod) % mod;
                    f[i][j][1] = (f[i + 1][j][0] + f[i + 1][j][1]) % mod;
                    if(s[i + 1][j] == 'R') f[i][j][1] = (f[i][j][1] - f[n - d[i + 1][j][1] + 1][j][0] + mod) % mod;
                }
            }
            printf("%lld\n", (f[1][1][1] + f[1][1][0]) % mod);
        }
        return 0;
    }

[https_codeforces.com_problemset_problem_1247_E]: https://codeforces.com/problemset/problem/1247/E