CodeForces-245H：Queries for Number of Palindromes（3-14：区间DP||回文串）

Times：5000ms；

Memory limit：262144 kB

给定字符串S（|S|<=5000），下标由1开始。然后Q个问题（Q<=1e6），对于每个问题，给定L，R，回答区间[L,R]里有多少个回文串。

请想出两种或者以上的方法。

------------------------分界线--------------------------

方法1：区间DP。

容斥一下，dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+ok[i][j]，(ok表示是否是个回文串)。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int dp[maxn][maxn],ok[maxn][maxn],N,Q;

char c[maxn];

void DP()

{

    for(int i=N;i>=;i--)

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

         if(j-i==) ok[i][j]=,dp[i][j]=;

         else if(j-i==) dp[i][j]=ok[i][j]=dp[i][i]+dp[j][j]+(c[i]==c[j]?:);

         else {

            ok[i][j]=ok[i+][j-]&(c[i]==c[j]);

            dp[i][j]=dp[i+][j]+dp[i][j-]-dp[i+][j-]+ok[i][j];

         }

    }

}

int main()

{

    scanf("%s",c+);

    N=strlen(c+);

    DP();

    scanf("%d",&Q);

    while(Q--){

        int x,y; scanf("%d%d",&x,&y);

        printf("%d\n",dp[x][y]);

    }

    return ;

}

方法2：

马拉车：每个为起点，然后预处理得到每个为起点的回文串个数前缀和。为了训练，就先不给带代码了。

方法3：回文树，这个我还不会。

方法4：暴力，开始我以为暴力得到回文串，然后差分得到前缀和，但是前缀和涉及到了交叉问题可能会导致出错。所以，目前还不行。（不过别人说可以，那再想想）

巴特西

CodeForces-245H：Queries for Number of Palindromes（3-14：区间DP||回文串）

最新文章

热门文章