DP VK Cup 2012 Qualification Round D. Palindrome pairs

 1 /*
 2     题意：在i前面找回文子串，在i后面找回文子串相互配对，问有几对
 3     DP：很巧妙的从i出发向两头扩展判断是否相同来找回文串
 4         dpr[i] 代表记录从0到i间的回文子串的个数，dpl[i] 代表记录i之后的回文子串个数
 5         两两相乘就行了
 6     详细解释：http://blog.csdn.net/shiyuankongbu/article/details/10004443
 7 */
 8 #include <cstdio>
 9 #include <algorithm>
10 #include <cmath>
11 #include <iostream>
12 #include <cstring>
13 #include <string>
14 #include <map>
15 #include <vector>
16 #include <set>
17 using namespace std;
18 
19 const int MAXN = 2000 + 10;
20 const int INF = 0x3f3f3f3f;
21 string s;
22 int dpr[MAXN];
23 int dpl[MAXN];
24 
25 bool ok(int x, int y)
26 {
27     int i, j;
28     for (i=x, j=y; i<=y && j>=x; ++i, --j)
29     {
30         if (s[i] != s[j])    return false;
31     }
32 
33     return true;
34 }
35 
36 int main(void)        //VK Cup 2012 Qualification Round D. Palindrome pairs
37 {
38     //freopen ("D.in", "r", stdin);
39 
40     while (cin >> s)
41     {
42         memset (dpr, 0, sizeof (dpr));
43         memset (dpl, 0, sizeof (dpl));
44         long long ans = 0;
45         int len = s.size ();
46 
47         for (int i=0; i<len; ++i)
48         {
49             for (int j=i, k=i; j>=0&&k<len&&s[j]==s[k]; --j, ++k)
50             {
51                 dpl[j]++;    dpr[k]++;
52             }
53             for (int j=i, k=i+1; j>=0&&k<len&&s[j]==s[k]; --j, ++k)
54             {
55                 dpl[j]++;    dpr[k]++;
56             }
57         }
58 
59         for (int i=1; i<len; ++i)
60             dpr[i] += dpr[i-1];
61 
62         for (int i=0; i<len-1; ++i)
63         {
64             ans += dpr[i] * dpl[i+1];
65         }
66 
67         cout << ans << endl;
68     }
69 
70 
71     return 0;
72 }