每日一题 5月29日 管道取珠 多人游戏DP

题目链接：https://ac.nowcoder.com/acm/problem/17621

#include <bits/stdc++.h>
#define LL long long
using namespace std;

char s[100005], t[100005];
LL f[2][510][510];
const int mod=1024523;
int main(){
    int n, m; scanf("%d%d", &n, &m);
    scanf("%s%s", s+1, t+1);
    reverse(s + 1 , s + n + 1);
    reverse(t + 1 , t + m + 1);
    int pos=0; f[0][0][0]=1;
    for(int i=0; i<=n; i++, pos^=1){
        //memset(f[pos], 0, sizeof(f[pos]));
        for(int j=0; j<=m; j++){
            for(int k=0; k<=n; k++){
                if(i+j-k<0||i+j-k>m) continue;
                if(s[i+1]==s[k+1]){
                    f[pos^1][j][k+1]+=f[pos][j][k]; f[pos^1][j][k+1]%=mod;
                }
                if(s[i+1]==t[(i+j-k)+1]){
                    f[pos^1][j][k]+=f[pos][j][k]; f[pos^1][j][k]%=mod;
                }
                if(t[j+1]==s[k+1]){
                    f[pos][j+1][k+1]+=f[pos][j][k]; f[pos][j+1][k+1]%=mod;
                }
                if(t[j+1]==t[(i+j-k)+1]){
                    f[pos][j+1][k]+=f[pos][j][k]; f[pos][j+1][k]%=mod;
                }
                f[pos][j][k]=0;//这个状态已经发生转移，一定用不到了。
                //cout<<i<<" "<<j<<" "<<k<<" "<<f[pos][j][k]<<endl;
            }
        }
    }
    printf("%lld\n", f[pos][m][n]);

    return 0;
}