CF 570E dp递推

浅浅的花香味﹌ 2022-05-07 23:30 174阅读 0赞

题意：给一个n\*m的小写字母地图，找从（1，1）到（n，m）点非升路径，且路径组成的字符串是回文串的路径个数。

思路：

考虑从两端同时走，然后在中间相遇，走的步数是确定的，为n+m-1，

所以只要两边同时走（n+m）/2步就行；

考虑dp递推，只要条件限制好，是可以递推的

设dp\[step\]\[x1\]\[y1\]\[x2\]\[y2\]为走step步到达p1,p2两点匹配的路径个数。

转移方程就是

dp\[step\]\[x1\]\[y1\]\[x2\]\[y2\]=dp\[step-1\]\[x1\]\[y1-1\]\[x2\]\[y2-1\]+dp\[step-1\]\[x1\]\[y1-1\]\[x2-1\]\[y2\]+

dp\[step-1\]\[x1-1\]\[y1\]\[x2-1\]\[y2\]+dp\[step\]\[x1-1\]\[y1\]\[x2\]\[y2-1\];

这样的话空间时间都受不了，有些是没有必要的，比如step可以用滚动数组变成2，然后设一个计数器

step知道，x知道，y就确定，所以没必要用y，这样空间就是5e5，时间是1e7

#include<bits/stdc++.h>
    using namespace std;
    const int mo=1e9+7;
    const int N=510;
    typedef long long ll;
    ll dp[2][N][N];
    char s[N][N];
    
    int main(){
        int n, m;
        scanf("%d%d", &n, &m);
    
        for(int i=1; i<=n; i++){
            scanf("%s", s[i]+1);
        }
        int up;
        if((n+m)&1)
            up=(n+m-1)>>1;
        else
            up=(n+m)>>1;
        int cur=0, nxt=1;
        if(s[1][1]==s[n][m])
            dp[cur][1][n]=1;
        for(int step=2; step<=up; step++){
    
            for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) dp[nxt][i][j]=0;
            //printf("step: %d\n", step);
            int ll=min(n, step);
            for(int x1=1; x1<=ll; x1++){
                int y1=step-x1+1;
                int hh=max(1, n-step+1);
                for(int x2=n; x2>=hh; x2--){
                    int y2= m-(step-(n-x2+1));
                    //printf("(%d,%d) (%d,%d)\n", x1, y1, x2, y2);
    
                    if(x1<=x2 && s[x1][y1]==s[x2][y2]){
                        dp[nxt][x1][x2]=dp[cur][x1-1][x2] + dp[cur][x1-1][x2+1] +
                        dp[cur][x1][x2] + dp[cur][x1][x2+1];
                        dp[nxt][x1][x2]%=mo;
    
                        //printf("%lld %lld %lld %lld\n", dp[cur][x1-1][x2], dp[cur][x1-1][x2+1], dp[cur][x1][x2], dp[cur][x1][x2+1]);
    
                        //printf("(%d, %d) (%d, %d) %lld\n", x1, y1, x2, y2, dp[nxt][x1][x2]);
                    }
                }
            }
            swap(cur, nxt);
        }
    
        ll ans=0;
    
        for(int i=1; i<=n; i++){
            if((n+m)&1){
                ans=(ans+dp[cur][i][i+1]+dp[cur][i][i])%mo;
            }
            else{
                ans=(ans+dp[cur][i][i])%mo;
            }
        }
        printf("%I64d\n", ans);
    
        return 0;
    }