UVA 1362 - Exploring Pyramids（计数有关问题+区间DP）
UVA 1362 - Exploring Pyramids（计数问题+区间DP）
题目链接：1362 - Exploring Pyramids
白书上的例题，思路是对于每个结点，往后遍历分为左右两边子树来考虑，左边的子树为去掉根节点剩下的子树，而右边是要算上根节点的，这样就不会有重复的情况出现，然后根据乘法原理，左右两边情况相乘为总情况数，然后计算这些总和。
f[i][j]表示[i,j]结点的情况种数，那么 f[i][j] = sum{f[i + 1][k - 1] * f[k][j]}，并且s[i] == s[k] == s[j]，因为i, j, k表示的是根节点必须相同。
代码：
#include <stdio.h>
#include <string.h>
const int N = 305;
const int MOD = 1000000000;
char str[N];
int n;
long long f[N][N];
int main() {
while (~scanf("%s", str)) {
memset(f, 0, sizeof(f));
n = strlen(str);
for (int len = 0; len < n; len += 2) {
for (int l = 0; l + len < n; l++) {
int r = l + len;
if (l == r) f[l][r] = 1;
for (int k = l + 2; k <= r; k+= 2) {
if (str[l] == str[k] && str[k] == str[r]) {
f[l][r] = (f[l][r] + f[l + 1][k - 1] * f[k][r]) % MOD;
}
}
}
}
printf("%lld\n", f[0][n - 1]);
}
return 0;
}