HDU_5617Jam's maze

이 문제는 처음에 약간 흐리멍덩해 보였는데 먼저 DP가 생각났다. 이 행렬은 너무 뚜렷하지만 상태 이동 방정식을 어떻게 해야 하는지 잘 알고 데이터량이 좀 크다.사실 이렇게 이해할 수 있다. (1,1)과 (n,n)을 동시에 가운데로 가게 하고 중간에서 합쳐서 f[x1][y1][y1][y2]를 초기점에서 (x1,y1)(x2,y2) 두 점으로 정의할 때 구성된 서브열이 같은 방안수를 정의한다. 예를 들어 제목의 예에서 f[1][2][3][4]는 1과 같아야 한다. 왜냐하면'AB'라는 서브열을 동시에 구성하기 때문이다.좋습니다. 그럼 상태 이동 방정식이 f[x1][y1][x1][y1]=f[x1][y1-1][x2][y2+1]+f[x1][y1-1][x2+1][y2]+f[x1][y1][y1][y2][y2+1]+f[x1-1][y1][x2+1][y2].그러나 분명히 이렇게 하면 메모리가 폭발할 수 있기 때문에 최적화해야 한다. 새로운 변수 i는 이미 걸음걸이가 왔다는 것을 나타낸다. 그러면 y1=i-x1+2, y2=2*n-(x2+i).자, 그럼 현재 상태 이동 방정식은 이렇게 f[i][x1][x2]가 됩니다.참, 공간을 절약하기 위해 걸음수 1차원에 스크롤 그룹을 사용했어요.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#include <vector>
using namespace std;
#define N 500010
#define pi acos(-1.0)
#define mod 5201314
#define inf 0x3f3f3f3f
#define pb(x) push_back((x))
typedef long long ll;
typedef unsigned long long ull;
char a[510][510];
int dp[2][510][510];
int main(){
    int n,t,y1,y2;
    scanf("%d",&t);
    while(t--){
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%s",&a[i]);
        }
        int p=0;
        dp[0][1][n]=(a[1][0]==a[n][n-1]);
        for(int i=1;i<n;i++){
            for(int k=1;k<=n;k++)
              for(int j=1;j<=n;j++) 
                dp[!p][j][k]=0;
            for(int x1=1;x1<=i+1;x1++){
                for(int x2=n;x2>=n-i;x2--){
                    y1=i-x1+2;
                    y2=2*n-(x2+i);
                    if(a[x1][y1-1]!=a[x2][y2-1]) continue;
                    dp[!p][x1][x2]=(dp[!p][x1][x2]+dp[p][x1][x2])%mod;
                    dp[!p][x1][x2]=(dp[!p][x1][x2]+dp[p][x1][x2+1])%mod;
                    dp[!p][x1][x2]=(dp[!p][x1][x2]+dp[p][x1-1][x2])%mod;
                    dp[!p][x1][x2]=(dp[!p][x1][x2]+dp[p][x1-1][x2+1])%mod;
                }
            }
            p=!p;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=dp[p][i][i];
        }
        printf("%d
",ans%mod);
    }
    return 0;
}