HDU 5617 Jam's maze 巧妙DP

题意：给你一个字符矩阵，从（1，1）到（n，n）有很多种走法，每一种走法形成一个字符串，问有多少种走法形成的字符串是回文的

分析：（粘贴BC题解）

的是回文串，有人会想到后缀数组自动机马拉车什么的，其实只要求方案数很多，所以我们应该想到动态规划，首先是状态的定义，我们可以想着从(1,1)(1,1)和(n,n)(n,n)开始走，然后走到相遇。所以我们定义状态可以定义为f[x_1][y_1][x_2][y_2]f[x1][y1][x2][y2]表示所对应的两个点(x_1,y_1)(x_2,y_2)(x1,y1)(x2,y2)，这样的话考虑到数据的范围，显然会爆空间，然后我们想一想就是走多少步和知道x_1,x_2x1,x2的位置，就可以确定y_1,y_2y1,y2的位置。于是我们把状态定义为f[i][x_1][x_2]f[i][x1][x2]即可，状态转移很显然，如果相等的话把四个方向都扫一下即可。因为还是会爆空间，所以我们把第一维改成滚动数组就解决问题

注：其实这个题解的意思就是从1，1 和n，n 开始按距离斜着更新，最后统计相遇的地方，相遇显然就是dp[n-1][i][i]

难点就是斜着更新不好想，还有就是滚动数组的空间优化

然后附上丑的代码；

#pragma comment(linker,"/STACK:102400000,102400000")

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <cmath>

#include <climits>

#include <iostream>

#include <algorithm>

#include <map>

#include <set>

#include <stack>

#include <queue>

#include <string>

#include <list>

#include <bitset>

#include <vector>

#include <cassert>

using namespace std;

const int maxn=;

const int mod=;

int dp[][maxn][maxn];

char s[maxn][maxn];

int T,n;

void add(int &x,int y)

{

    x+=y;

    if(x>mod)x-=mod;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;++i)

         scanf("%s",s[i]+);

        if(s[][]!=s[n][n])

        {

           printf("0\n");

           continue;

        }

        int cur=;

        memset(dp[cur],,sizeof(dp[cur]));

        dp[cur][][n]=;

        for(int i=;i<n;++i)

        {

          cur^=;

          memset(dp[cur],,sizeof(dp[cur]));

          for(int x1=;x1<=i+;++x1)

          {

             for(int x2=n;x2>=n-i;--x2)

             {

                  int y1=i+-x1;

                  int y2=n*-x2-i;

                  if(s[x1][y1]!=s[x2][y2])continue;

                  add(dp[cur][x1][x2],dp[cur^][x1][x2]);

                  add(dp[cur][x1][x2],dp[cur^][x1][x2+]);

                  add(dp[cur][x1][x2],dp[cur^][x1-][x2]);

                  add(dp[cur][x1][x2],dp[cur^][x1-][x2+]);

             }

          }

        }

        int ans=;

        for(int i=;i<=n;++i)

          add(ans,dp[cur][i][i]);

       printf("%d\n",ans);

    }

    return ;

}

秒客网

HDU 5617 Jam's maze 巧妙DP

相关文章