Codeforces 245H Queries for Number of Palindromes：区间dp

题目链接：http://codeforces.com/problemset/problem/245/H

题意：

　　给你一个字符串s。

　　然后有t个询问，每个询问给出x,y，问你区间[x,y]中的回文子串的个数。

题解：

　　表示状态：

　　　　dp[x][y] = numbers

　　　　表示区间[x,y]中的回文子串个数。

　　找出答案：

　　　　每次询问：ans = dp[x][y]

　　如何转移：

　　　　dp[x][y] = dp[x][y-1] + dp[x+1][y] - dp[x+1][y-1] + pal[x][y]

　　　　用到了容斥原理。

　　　　pal[x][y]表示子串s[x to y]是否是一个回文串（是为1，不是为0）。

　　　　其中pal[x][y]又有递推式：

　　　　pal[x][y] = ( s[x]==s[y] && (x+1==y || pal[x+1][y-1]) )

　　　　记忆化搜索就好啦。

　　边界条件：

　　　　if(x>y) dp[x][y] = 0

　　　　if(x==y) dp[x][y] = 1

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 5005

 using namespace std;

 int t;

 int dp[MAX_N][MAX_N];

 int pal[MAX_N][MAX_N];

 char s[MAX_N];

 int is_pal(int x,int y)

 {

     if(s[x]!=s[y]) return ;

     if(x+==y) return ;

     if(pal[x+][y-]!=-) return pal[x+][y-];

     return pal[x+][y-]=is_pal(x+,y-);

 }

 int dfs(int x,int y)

 {

     if(dp[x][y]!=-) return dp[x][y];

     if(x>y) return ;

     if(x==y) return dp[x][y]=pal[x][y]=;

     dp[x][y]=dfs(x,y-)+dfs(x+,y)-dfs(x+,y-);

     pal[x][y]=(s[x]==s[y] && (x+==y || pal[x+][y-]));

     return dp[x][y]=dp[x][y]+pal[x][y];

 }

 int main()

 {

     scanf("%s%d",s+,&t);

     memset(dp,-,sizeof(dp));

     int x,y;

     while(t--)

     {

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

         printf("%d\n",dfs(x,y));

     }

 }

巴特西

Codeforces 245H Queries for Number of Palindromes：区间dp

最新文章

热门文章