codeforces 570 E. Pig and Palindromes (DP)

题目链接：

题目描述：

　　有一个n*m的矩阵，每个小格子里面都有一个字母。Peppa the Pig想要从(1,1)到(n, m)。因为Peppa the Pig是一个完美主义者，她想要她所经过的路径上的字母组成的字符串是一个回文串，现在Peppa the Pig想要知道有多少满足条件的走法？

解题思路：

　　因为经过路径上的字母要组成回文串，所以可以从(1,1),(n,m)同时开始dp。从(1,1)出发只能向下方和右方走，从(n,m)出发只能向上方和左方走。然后就可以dp[x1][y1][x2][y2]，其实呢可以把dp数组优化到三维dp[step][x1][x2]。因为从两点出发走过的步数是一样的，知道了走过的步数和一个方向的坐标，就可以求出另一个方向的坐标咯。但是酱紫搞的话，还是会MTL的(亲身经历>_<)······，但是请我们尊贵的滚动数组出场就一切ok咯。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 int dp[][maxn][maxn], n ,m;

 char maps[maxn][maxn];

 int main ()

 {

     while (scanf ("%d %d", &n, &m) != EOF)

     {

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

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

         if (maps[][] != maps[n][m])

         {

             printf ("0\n");

             continue;

         }

         memset (dp, , sizeof(dp));

         dp[][][n] = ;

         int res = (n + m - ) / ;

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

         {

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

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

                 {

                     int x1, x2, y1, y2;

                     x1 = j, y1 = i - j + ;

                     x2 = k, y2 = n + m - k - i;

                     if (maps[x1][y1] == maps[x2][y2])

                     {

                         if (x1>x2 || y1>y2)

                             continue;

                         dp[i%][j][k] = (dp[i%][j][k] + dp[(i%)^][j-][k])%mod;

                         dp[i%][j][k] = (dp[i%][j][k] + dp[(i%)^][j-][k+])%mod;

                         dp[i%][j][k] = (dp[i%][j][k] + dp[(i%)^][j][k])%mod;

                         dp[i%][j][k] = (dp[i%][j][k] + dp[(i%)^][j][k+])%mod;

                     }

                 }

             memset(dp[(i%)^], , sizeof(dp[(i%)^]));

         }

         int ans = ;

         if ((n+m)% == )

         {

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

                 ans = (ans + dp[res%][i][i]) % mod;

         }

         else

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

             {

                 int x = res - i + ;

                 if (x +  <= m)

                     ans = (ans + dp[res%][i][i]) % mod;

                 if (i +  <= n)

                     ans = (ans + dp[res%][i][i+]) % mod;

             }

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

     }

     return ;

 }

巴特西

codeforces 570 E. Pig and Palindromes (DP)

最新文章

热门文章