CODEFORCE 159D

readme.md

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

cf159d.cpp

#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;
}

cf159d.py

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)])