[DP][后效性处理] codeforces 1247 E Rock Is Push

题目链接

题意：

给定一个 $n*m$ 的棋盘，每次你只能向右走或者向下走，要求从左上角 $(1,1)$ 走到右下角 $(n,m)$ ，问有多少种走法。
有一个限制因素是棋盘的格子里可能有石头，然后走到一个地方就会把这里的石头按照来的方向推出去，如果有多个石头就会连带着一起推过去。
数据范围 $1\le n,m\le 2000$ ，答案对 $10^9+7$ 取模。

题解：

直接DP会有后效性的问题，我们可以给状态加上约束：令 $D_{i,j} R_{i,j}$ 分别表示一个点改变原方向后向下走/向右走有多少种走法。
这样的话dp转移可以写成类似于 $D_{i,j}=\sum_{i=1}^{n-k-i}R_{i+t,j}$ 的形式，然后这样可以得到一个复杂度 $\mathcal{O}(n^3)$ 的算法，
观察这个式子发现他是线性的，当一个维度发生变化是等式右边只有一到两项会发生变化，就把复杂度降到了 $\mathcal{O}(n^2)$ ,就可以通过本题了。

wa点：

• 最终的边界没有考虑好是最大的wa点
• 其次是吃完饭回来忘记取模了emmmmm

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=2e3+5;
const int mod=1e9+7;

char ori[maxn][maxn];
ll low[maxn][maxn],rgt[maxn][maxn];
pair<ll,ll > dpp[maxn][maxn];
int n,m;

pair<ll,ll> dp(int x,int y){
    
    if(dpp[x][y].first!=-1) return dpp[x][y];
    dpp[x][y].first=dpp[x][y].second=0;
    if(x+low[x][y]>=n) dpp[x][y].first=0;
    else{
        if(x+1==n&&y==m) dpp[x][y].first=dp(x+1,y).second;
        else dpp[x][y].first=dp(x+1,y).first+dp(x+1,y).second;
        if(ori[x+1][y]) dpp[x][y].first-=dp(n-low[x][y]+1,y).second;
    }
    if(y+rgt[x][y]>=m) dpp[x][y].second=0;
    else{
        if(x==n&&y+1==m) dpp[x][y].second=dp(x,y+1).first;
        else dpp[x][y].second=dp(x,y+1).second+dp(x,y+1).first;
        if(ori[x][y+1]) dpp[x][y].second-=dp(x,m-rgt[x][y]+1).first;
    }
    dpp[x][y].first%=mod;dpp[x][y].second%=mod;
    return dpp[x][y];
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;if(n==1&&m==1){ char c;cin>>c;cout<<(c=='.'?1:0);return 0; }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>ori[i][j],ori[i][j]=(ori[i][j]=='.'?0:1),dpp[i][j].first=dpp[i][j].second=-1;
    if(ori[n][m]==1){cout<<0;return 0;}
    for(int i=n;i>=1;--i) for(int j=m;j>=1;--j) low[i][j]=low[i+1][j]+ori[i][j],rgt[i][j]=rgt[i][j+1]+ori[i][j];
    for(int i=n;i>=1;--i) for(int j=m;j>=1;--j) low[i][j]-=ori[i][j],rgt[i][j]-=ori[i][j];
    dpp[n][m].first=(!(m==1)),dpp[n][m].second=(!(n==1));
    cout<<((dp(1,1).first+dp(1,1).second)%mod+mod)%mod<<"\n";
    return 0;
}