rock is push 这道题我看的时候第一反应是记忆化搜索，但是仔细想想，一共有2nm种状态，并且每种状态都有次数在0-max(n,m)的转移，这么说的话，复杂度接近O(N^3),本人也试了一次，果然tle. 现在就要从状态转移方程中找到可以优化的地方了。这道题的部分状态转移方程(先设定0是向右，1是向下)： dp[i][j][0]=dp[i][j+1][1]+dp[i][j+2][1]+dp[i][j+2][1]+…dp[i][k][1] 也就是说，一个点下一步是向右走的次数可以转移到与该点同行且位于该点右边的所有可行点向下走的次数之和。我们可以先边算边处理每行的关于dp[i][j][1]的后缀和，这样当我们算一个新的状态时，我们只要找到该状态的k为多少，用已经算好的后缀和减去以k+1为头的后缀和，就是答案了。优化的手段和单调队列有些类似。至于k，只和该行的障碍物有关。 因为障碍物的存在，你的箱子不能推到底，也就是推到m列的位置，有多少个障碍物与该点同行且在该点右边，就会阻碍多少种情况，所以k应该为m减去与该点同行的且在该点右边的障碍数，用x表示障碍数，用sumr[i][j]表示dp[i][j][1]在第i行，以m为起点，以j为终点的后缀和的话，那么dp[i][j][0]=sumr[i][j]-sumr[i][k+1]，k=m-x； 对于向下的转移用同样的方式处理。
#include<cstring> #include<stdio.h> #include<cmath> #include<map> #include<vector> #include<set> #include<sstream> #include<queue> #include<algorithm> #include<stack> #include<cstdlib> #include<deque> #include<bitset> #include<iostream> #define FIN freopen("D://debug//in.txt","r",stdin); #define FOUT freopen("D://debug//out.txt","w",stdout); #define FDATA freopen("D://debug//data.txt","w",stdout); using namespace std; typedef long long int ll; const int maxn=2e3+5; const int mod=1e9+7; int n,m,dp[maxn][maxn][2]; char s[maxn][maxn]; int row[maxn][maxn]; int col[maxn][maxn]; int sumr[maxn][maxn],sumc[maxn][maxn]; int main(){ //FIN //FOUT cin>>n>>m; for(int i=1;i<=n;i++){ cin>>s[i]+1; } for(int i=1;i<=n;i++){ for(int j=m;j>=1;j--){ row[i][j]=row[i][j+1]+(s[i][j]=='R'); } } for(int i=1;i<=m;i++){ for(int j=n;j>=1;j--){ col[j][i]=col[j+1][i]+(s[j][i]=='R'); } } if(n==1&&m==1){ puts("1");return 0; } if(s[n][m]=='R'){ puts("0");return 0; } memset(dp,0,sizeof(dp)); memset(sumr,0,sizeof(sumr)); memset(sumc,0,sizeof(sumc)); dp[n][m][0]=dp[n][m][1]=1; sumr[n][m]=sumc[n][m]=1; for(int i=n;i>=1;i--){ for(int j=m;j>=1;j--){ if(i==n&&j==m)continue; int x=row[i][j+1]; dp[i][j][0]=(sumr[i][j+1]-sumr[i][m-x+1]+mod)%mod; int y=col[i+1][j]; dp[i][j][1]=(sumc[i+1][j]-sumc[n-y+1][j]+mod)%mod; sumr[i][j]=(sumr[i][j+1]+dp[i][j][1])%mod; sumc[i][j]=(sumc[i+1][j]+dp[i][j][0])%mod; } } printf("%d\n",(dp[1][1][1]+dp[1][1][0])%mod); }