Queries for Number of Palindromes
Problem's Link: http://codeforces.com/problemset/problem/245/H
Mean:
给你一个字符串，然后q个询问：从i到j这段字符串中存在多少个回文串。
analyse:
dp[i][j]表示i~j这段的回文串数。
首先判断i~j是否为回文，是则dp[i][j]=1,否则dp[i][j]=0;
那么dp[i][j]=dp[i][j]+dp[i][j-1]+dp[i+1[j]-dp[i+1][j-1]，从后往前推;
注意判断dp[i][j]是否是回文也需要从后往前推，否则超时。
Time complexity: O(n*n)
Source code:
// Memory Time
// 1347K 0MS
// by : crazyacking
// 2015-03-31-16.17
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define MAXN 5005
#define LL long long
using namespace std;
char str[MAXN];
int dp[MAXN][MAXN]; bool judge(int sta,int en)
{
for(int i=sta,j=en;i<j;++i,--j)
{
if(str[i]!=str[j])
return false;
}
return true;
}
int main()
{
gets(str);
int len=strlen(str);
memset(dp,,sizeof dp);
for(int i=;i<len;++i)
{
if(str[i]==str[i+])
dp[i][i+]=;
dp[i][i]=;
}
for(int i=len-;i>=;--i)
{
for(int j=i;j<len;++j)
{
if(dp[i+][j-]==&&str[i]==str[j])
dp[i][j]=;
}
}
for(int i=len-;i>=;--i)
{
for(int j=i;j<len;++j)
{
dp[i][j]=dp[i][j]+dp[i][j-]+dp[i+][j]-dp[i+][j-];
}
}
int q;
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d %d",&x,&y);
printf("%d\n",dp[x-][y-]);
}
return ;
}