题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=27623#problem/D
题目大意：给你一串字符串，在满足第一个回文串右边小于第二个回文串左边的情况下，能组成多少个回文串。
解题思路：个人感觉是一道不错的dp题，先预处理出所有的f[i][j]，f[i][j]表示i到j是否是一个回文串。这里比较巧妙的利用到一点dp，如果字符i等于字符j，那么 f[i][j]=f[i+1][j-1]。然后再预处理出前i个字符能组成的回文串数，再求解。
这题开始没考虑清楚，我是枚举所有分界点，处理两边的字串，出问题了，因为这样会重复处理...
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long lld; 8 const int maxn=2222; 9 int f[maxn][maxn], sum[maxn]; 10 char s[maxn]; 11 12 int main() 13 { 14 while(cin >> s) 15 { 16 memset(f,0,sizeof(f)); 17 int len=strlen(s); 18 for(int i=0; i<len; i++) f[i][i]=1; 19 for(int i=1; i<len; i++) ///枚举间隔 20 for(int j=0; j<len; j++) 21 { 22 int k=j+i; 23 if(k<len&&s[j]==s[k]) 24 { 25 if(i==1) f[j][k]=1; 26 else f[j][k]=f[j+1][k-1]; ///根据中间包夹的字符串推出现在的串是否为回文串，很巧妙 27 } 28 } 29 memset(sum,0,sizeof(sum)); 30 for(int i=0; i<len; i++) 31 for(int j=0; j<len; j++) 32 if(i+j<len&&f[j][j+i]) sum[j+i]++; 33 for(int i=1; i<len; i++) sum[i]+=sum[i-1]; 34 lld ans=0; 35 for(int i=1; i<len; i++) ///以i为分界点 36 for(int j=i; j<len; j++) 37 if(f[i][j]) ans+=sum[i-1]; 38 cout << ans <<endl; 39 } 40 return 0; 41 }