CodeForces 570 E.Pig and Palindromes(组合数学+dp)_ZSQ-程序员宅基地

技术标签: Code Forces  dp  组合数学  

Description

给出一个 n×m 的字符矩阵,称一条从 (1,1) (n,m) 的路径是合法的当且仅当每一步只能往右走或往下走,且路径上位置的字符组成串是一个回文串,问合法路径条数

Input

第一行两个整数 n,m 表示矩阵行列数,之后输入一个只由小写字母组成的 n×m 的字符矩阵 (1n,m500)

Output

输出合法路径数,结果模 109+7

Sample Input

3 4
aaab
baaa
abba

Sample Output

3

Solution

(1,1) (n,m) 开始往中间走,枚举步数 s ,第一个点往下走到 x1 行,第二个点往上走到达 x2 行,那么就可以得到这两个点的坐标为 (x1,y1=sx1+2) (x2,y2=m(s(nx2))) ,以 dp[st][x1][x2] 表示两个点走到该位置时所经过的路径上字符串完全相同的方案数,如果 (x1,y1) (x2,y2) 这两个位置上的字符相同,那么就可以从一些能够走到这两点的状态转移过来,即

dp[s][x1][x2]=dp[s1][x11][x2]+dp[s1][x1][x2+1]+dp[s1][x1][x2]+dp[s1][x11][x2+1]

O(n3) 的复杂度可以得到 dp ,最终两个点会分别走 cnt=n+m21 步,如果 n+m1 是奇数,那么最后两个点必须要走到同一行,答案为 i=1ndp[cnt][i][i] ,如果 n+m1 是偶数,那么走完后两个点可能不在同一行,但最多只能差一行,故答案还需加上 i=1n1dp[cnt][i][i+1]

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=505;
#define mod 1000000007
int n,m,dp[2][maxn][maxn];
char s[maxn][maxn];
void add(int &x,int y)
{
    x=x+y>=mod?x+y-mod:x+y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    if(s[1][1]!=s[n][m])printf("0\n");
    else
    {
        dp[0][1][n]=1;
        int cur=0;
        for(int i=1;i<(n+m)/2;i++)
        {
            cur^=1;
            memset(dp[cur],0,sizeof(dp[cur]));
            for(int x1=1;x1<=i+1;x1++)
                for(int x2=n;x2>=n-i;x2--)
                {
                    int y1=i-x1+2,y2=m-(i-(n-x2));
                    if(x1>x2||y1>y2)continue;
                    if(s[x1][y1]!=s[x2][y2])continue;
                    add(dp[cur][x1][x2],dp[cur^1][x1-1][x2]);
                    add(dp[cur][x1][x2],dp[cur^1][x1][x2+1]);
                    add(dp[cur][x1][x2],dp[cur^1][x1][x2]);
                    add(dp[cur][x1][x2],dp[cur^1][x1-1][x2+1]);
                }
        }
        int ans=0;
        for(int i=1;i<=n;i++)add(ans,dp[cur][i][i]);
        if((n+m-1)%2==0)
            for(int i=1;i<n;i++)add(ans,dp[cur][i][i+1]);
        printf("%d\n",ans);
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/V5ZSQ/article/details/79038510

智能推荐

随便推点