题目链接：
codeforces 245H
题目大意：
给出一个字符串，询问任意区间内的回文子串的个数。
题目分析：定义isPar[i][j]表示区间字符串[i,j]是否是回文，可以通过isPar[i+1][j-1]递推得到。定义dp[i][j]表示及区间[i,j]内的回文子串的个数，转移方程如下：
用到了一点容斥的思想。 AC代码：;char s[MAX];int n,q,dp[MAX][MAX];int isPar[MAX][MAX];int check ( int l , int r ){if ( l == r ) return 1;if ( s[l] != s[r] ) return 0;if ( r-l == 1 ) return 1;if ( isPar[l+1][r-1] ) return 1;return 0;}int main ( ){while ( ~scanf ( “%s” , s ) ){int n = strlen ( s );memset ( isPar , 0 , sizeof ( isPar ) );for ( int i = 0 ; i < n ; i++ )dp[i][i] = 1;for ( int i = 0 ; i < n ; i++ )for ( int j = 0 ; j+i < n ; j++ ){int k = j+i;isPar[j][k] = check ( j , k );}for ( int i = 1 ; i < n ; i++ ){for ( int j = 0 ; j+i <n ; j++ ){int k = j+i;dp[j][k] = dp[j][k-1] + dp[j+1][k];if ( i > 1 )dp[j][k] -= dp[j+1][k-1];dp[j][k] += isPar[j][k];}}scanf ( “%d” , &q );while ( q– ){int l,r;scanf ( “%d%d” , &l , &r );l–,r–;printf ( “%d\n” , dp[l][r] );}}}
，两粒种子，一片森林。
