CROC-MBTU 2012, Elimination Round (ACM-ICPC) H. Queries for Number of Palindromes 区间DP
链接：
http://codeforces.com/contest/245/problem/H
题意：
给你一个字符串，每次询问l，r区间有多少个回文子串
题解：
定义isPar[i][j]表示区间字符串[i,j]是否是回文，可以通过isPar[i+1][j-1]递推得到。
定义dp[i][j]表示及区间[i,j]内的回文子串的个数，转移方程如下：
]
这道题就算关了同步用cin,cout也会超时。。
代码：
31 string s; 32 bool isPar[MAXN][MAXN]; 33 int dp[MAXN][MAXN]; 34 35 bool check(int l, int r) { 36 if (l == r) return true; 37 if (s[l] != s[r]) return false; 38 if (r - l == 1) return true; 39 if (isPar[l + 1][r - 1]) return true; 40 return false; 41 } 42 43 int main() { 44 cin >> s; 45 int n = s.length(); 46 rep(len, 0, n) rep(i, 0, n - len) { 47 int j = i + len; 48 isPar[i][j] = check(i, j); 49 } 50 rep(i, 0, n) dp[i][i] = 1; 51 rep(len, 1, n) rep(i, 0, n - len) { 52 int j = i + len; 53 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + isPar[i][j]; 54 if (len > 1) dp[i][j] -= dp[i + 1][j - 1]; 55 } 56 int q; 57 cin >> q; 58 while (q--) { 59 int l, r; 60 scanf("%d%d", &l, &r); 61 l--, r--; 62 printf("%d ", dp[l][r]); 63 } 64 return 0; 65 }