http://codeforces.com/contest/245/problem/H
题意:给定一个字符串，每次给个区间，求区间内有几个回文串(n<=5000)
思路:设定pd[i][j]代表i~j这部分是不是一个回文串，这个可以n^2预处理
然后设定f[i][j]代表i~j区间有多少个回文串，由于满足区间加减，因此有
f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+pd[i][j]
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
int pd[][],f[][],n;
char s[];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void init(){
for (int i=;i<=n;i++)
pd[i][i]=;
for (int len=;len<=n;len++)
for (int i=;i+len-<=n;i++){
int j=i+len-;
if (i==j-&&s[i]==s[j]) pd[i][j]=;
else
if (s[i]==s[j]) pd[i][j]|=pd[i+][j-];
}
for (int i=;i<=n;i++)
f[i][i]=;
for (int i=;i<n;i++)
if (s[i]==s[i+])
f[i][i+]=;
else
f[i][i+]=;
for (int len=;len<=n;len++)
for (int i=;i+len-<=n;i++){
int j=i+len-;
f[i][j]=f[i+][j]+f[i][j-]-f[i+][j-]+pd[i][j];
}
}
int main(){
scanf("%s",s+);
n=strlen(s+);
init();
int T=read();
while (T--){
int l=read(),r=read();
printf("%d\n",f[l][r]);
}
return ;
}