DP VK Cup 2012 Qualification Round D. Palindrome pairs

题目地址:http://blog.csdn.net/shiyuankongbu/article/details/10004443

 /*
题意:在i前面找回文子串,在i后面找回文子串相互配对,问有几对
DP:很巧妙的从i出发向两头扩展判断是否相同来找回文串
dpr[i] 代表记录从0到i间的回文子串的个数,dpl[i] 代表记录i之后的回文子串个数
两两相乘就行了
详细解释:http://blog.csdn.net/shiyuankongbu/article/details/10004443
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <set>
using namespace std; const int MAXN = + ;
const int INF = 0x3f3f3f3f;
string s;
int dpr[MAXN];
int dpl[MAXN]; bool ok(int x, int y)
{
int i, j;
for (i=x, j=y; i<=y && j>=x; ++i, --j)
{
if (s[i] != s[j]) return false;
} return true;
} int main(void) //VK Cup 2012 Qualification Round D. Palindrome pairs
{
//freopen ("D.in", "r", stdin); while (cin >> s)
{
memset (dpr, , sizeof (dpr));
memset (dpl, , sizeof (dpl));
long long ans = ;
int len = s.size (); for (int i=; i<len; ++i)
{
for (int j=i, k=i; j>=&&k<len&&s[j]==s[k]; --j, ++k)
{
dpl[j]++; dpr[k]++;
}
for (int j=i, k=i+; j>=&&k<len&&s[j]==s[k]; --j, ++k)
{
dpl[j]++; dpr[k]++;
}
} for (int i=; i<len; ++i)
dpr[i] += dpr[i-]; for (int i=; i<len-; ++i)
{
ans += dpr[i] * dpl[i+];
} cout << ans << endl;
} return ;
}
上一篇:VK Cup 2012 Qualification Round 1 C. Cd and pwd commands 模拟


下一篇:Spring Boot 2.0.1 入门教程