Codforces 570E Pig and Palindromes 题解（DP）

原题链接： 洛谷：点我QωQ CF：点我QωQ

题意简述

给定一个$n\ast m$的迷宫，由字符，初始在最左上角，每次只能向右，下走。在所有走到最右下角的路径中，有多少是回文的？

数据

输入

第一行两个正整数，$n,m(n,m<=500)$（注意$CF$的神评测姬上，$500^3$是稳过的） 接下来$n$行，每行$m$个字符，描述这个迷宫。

输出

输出有多少路径是回文的。

样例

输出 3 4 aaab baaa abba 输出 3 解释 $aaaaaa$ 有两条 $abaaba$ 有一条 一共三条

思路

这。。。是个计数$DP$？ 相信我是$DP$，因为这显然没有数学方法珂以做，当然也没有别的了，暴力枚举是$TLE$的，所以只能$DP$了。

如何设$dp$呢？一步一步来。我们设$dp[i][j]$为到$(i,j)$点的回文数，那么答案就是$dp[n][m]$了。如何转移呢？我们把总步数取一半，设为$Mid$，然后遍历从$(1,1)$开始走$mid$步能到的点，从这些点再走$Mid$步，看看是否能走到$(n,m)$并且两条路径组成的字符串相反（如$abc$和$cba$）。然后我们会发现，$wdnmd$不知道的太多了，没法转移。

就引起一个问题：我们要知道什么？

在上面的错误的$dp$中，我们把一个路径分成两半，是第$1$~$Mid$步和第$(Mid+1)$ ~ $n$步组成的。那么，我们能不能换一种方式想这个呢？

这个$两半$不禁让我们浮想联翩。是怎么样的两半呢？就在一瞬间，我们有了一个想法：

分成两个路，$A$路从$(1,1)$开始，$B$路从$(n,m)$开始，往中间相遇。

！！！这看起来真有道理，而且仿佛能转移。

设$dp[i][j][u][v]$表示$A$路走到$i,j$，$B$路走到$u,v$的情况数。当$(i,j)$位置和$(u,v)$位置上的字符相同时（否则就不回文了），有转移： $$\begin{gathered} dp[i][j][u][v] \\ =dp[i-1][j][u+1][v] \\ +dp[i-1][j][u][v+1] \\ +dp[i][j-1][u+1][v] \\ +dp[i][j-1][u][v+1] \end{gathered}$$ （一个小小的疑问：为啥$i,j$后面是$-1$，$u,v$后面是$+1$？） （解答：因为$i,j$是正着走的，$u,v$是反着走的，所以一正一负）

但是空间开不下。$500^4$显然时间空间都过不去吧？？？

但是我们想到一个优化。相同步数的情况下，点应该是按斜线分布的，如下图： （从$1,1$开始步数为$5$） 所以，只要确定了步数，确定了行左坐标，就能确定列坐标。设$dp[step][i][j]$表示$A$路走到第$i$行，$B$路走到第$j$行的情况数。那么，计算出行坐标，就珂以用类似上面的方法转移了。我们会发现，在整个转移过程中，$dp[step][i][j]$关系到的只有$dp[step-1]$的状态。所以我们考虑用滚动数组优化掉这个空间，空间就是$O(2nm)=O(nm)$了，时间约是$O(nm(n+m))=O(n^3)$。

代码:

#include<bits/stdc++.h> using namespace std; namespace Flandle_Scarlet { #define N 510 #define mod 1000000007 #define int long long char mp[N][N]; int n,m; void Input() { scanf("%I64d%I64d",&n,&m); for(int i=1;i<=n;++i) { scanf("%s",mp[i]+1); } if (mp[1][1]!=mp[n][m])//如果这两个位置不相等,显然没有解 { puts("0"); exit(0); } } int dp[2][N][N]; void DP() { dp[1][1][n]=1;//边界 int pos=1; for(int step=1;step<=((n+m)>>1);++step) { pos^=1;//滚动数组 memset(dp[pos],0,sizeof(dp[pos])); //滚动数组最大的坑:初始化 for(int i=1;i<=step;++i) { for(int j=n;j>=n-step+1;--j) { if (mp[i][step-i+1]==mp[j][(n+m-step+1)-j]) { dp[pos][i][j] =dp[pos^1][i][j] +dp[pos^1][i][j+1] +dp[pos^1][i-1][j] +dp[pos^1][i-1][j+1]; //差不多的转移... dp[pos][i][j]%=mod; } } } } int ans=0; if ((n+m)&1) { for(int i=1;i<=n;++i) { ans+=(dp[pos][i][i]+dp[pos][i][i+1])%mod; ans%=mod; } } else { for(int i=1;i<=n;++i) { ans+=dp[pos][i][i]; ans%=mod; } }//特判n+m的奇偶 printf("%I64d\n",ans); } void Main() { if (0) { freopen("","r",stdin); freopen("","w",stdout); } Input(); DP(); } }; main() { Flandle_Scarlet::Main(); return 0; }

回到总题解界面