Skip to content

Instantly share code, notes, and snippets.

@jo32
Last active October 15, 2015 14:42
Show Gist options
  • Save jo32/5d23d9723aba50e861f1 to your computer and use it in GitHub Desktop.
Save jo32/5d23d9723aba50e861f1 to your computer and use it in GitHub Desktop.
CODEFORCE 159D

cf159d.cpp 对应的是 cpp 版本的,AC 版本,和 cf159d.py 这个版本的算法是一样的,但是 python 版本怎么都是超时的,看来对 Python 的理解还是不够深。

#include <cstdio>
#include <cstring>
#include <iostream>
const int maxN = 2048;
int dpLR[maxN];
int dpRL[maxN];
bool dpPalin[maxN][maxN];
char s[maxN];
long long ans = 0;
int main() {
scanf("%s", s);
int len = strlen(s);
dpLR[0] = 1;
dpRL[len - 1] = 1;
for (int i = 0; i < len; i++) {
dpPalin[i][i] = true;
}
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
if (i - j > 1) {
dpPalin[j][i] = s[j] == s[i] && dpPalin[j + 1][i - 1];
} else {
dpPalin[j][i] = s[j] == s[i];
}
}
}
for (int i = 1; i < len; i++) {
int si = 0;
for (int j = 0; j < i; j ++) {
if (dpPalin[j][i] == true) {
si += 1;
}
}
dpLR[i] = dpLR[i - 1] + si + 1;
}
for (int i = len - 2; i >= 0; i--) {
int si = 0;
for (int j = len - 1; j > i; j--) {
if (dpPalin[i][j] == true) {
si += 1;
}
}
dpRL[i] = dpRL[i + 1] + si + 1;
}
for (int i = 0; i < len - 1; i ++) {
if (i - 1 >= 0) {
ans += (long long)(dpLR[i] * dpRL[i + 1] - dpLR[i - 1] * dpRL[i + 1]);
} else {
ans += (long long)(dpLR[i] * dpRL[i + 1]);
}
}
printf("%lld\n", ans);
return 0;
}
s = raw_input()
# dpLR[i] means the number of palindromes in s[0, i]
dpLR = [0] * len(s)
dpLR[0] = 1
# dpRL[i] means the number of palindromes in s[i, len(s) - 1]
dpRL = [0] * len(s)
dpRL[-1] = 1
# dpPalin[i][j] means is s[i, j] is a palindrome
dpPalin = [[False for i in xrange(len(s))] for i in xrange(len(s))]
for i in xrange(len(s)):
dpPalin[i][i] = True
for i in xrange(1, len(s)):
for j in xrange(i):
dpPalin[j][i] = s[j] == s[i] and (dpPalin[j + 1][i - 1] if i - j > 1 else True)
def isPalindrome(start, end):
return dpPalin[start][end]
for i in xrange(1, len(s)):
si = 0
for j in xrange(i):
if isPalindrome(j, i):
si += 1
dpLR[i] = dpLR[i - 1] + si + 1
for i in reversed(xrange(-len(s), -1)):
si = 0
for j in reversed(xrange(i + 1, 0)):
if isPalindrome(i, j):
si += 1
dpRL[i] = dpRL[i + 1] + si + 1
print sum([dpLR[i] * dpRL[i + 1] - (dpLR[i - 1] if i - 1 >= 0 else 0) * dpRL[i + 1] for i in xrange(len(s) - 1)])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment