「UVa 1362」Exploring Pyramids - 区间 DP + 计数原理

给定一棵树的欧拉序列,树的子节点是有序的,求有多少棵树满足这个欧拉序列。

链接

UVa 1362

题解

书上的解法,用 f(i, j) 表示欧拉序列 S 中的第 i 到第 j 个字符所表示的树的数量,则有:

  1. i = j 时, f(i, j) = 1
  2. S(i) \neq S(j) 时, f(i, j) = 0 ,因为欧拉序列的第一个点和最后一个点都必须是根节点。

欧拉序列的一个特点是,每一次回溯到根都会将根节点记录下来。所以我们可以枚举中转点 k ,当 i = k = j 时,递归计算 (i, k) 区间内(第一棵子树)的答案和 [k, j] 区间的答案(其它子树),并将其相乘。

多组数据一定要清数组,一定要清数组,一定要清数组 ……

代码

#include <cstdio>
#include <cstring>

const int MAXN = 300;
const long long MOD = 1000000000;

char str[MAXN + 1];

long long search(int i, int j, bool reset = false) {
    static long long mem[MAXN][MAXN];
    static bool calced[MAXN][MAXN];

    if (reset) {
        memset(mem, 0, sizeof(mem));
        memset(calced, 0, sizeof(calced));
    }

    long long &ans = mem[i][j];

    if (calced[i][j]) return ans;
    calced[i][j] = true;

    if (i == j) return ans = 1;
    else if (str[i] != str[j]) return ans = 0;
    else {
        ans = 0;
        for (int k = i + 2; k <= j; k++) {
            if (str[i] != str[k]) continue;
            ans += search(i + 1, k - 1) * search(k, j) % MOD;
            ans %= MOD;
        }
    }

    return ans;
}

int main() {
    for (; ~scanf("%s", str); printf("%lld\n", search(0, strlen(str) - 1, true)));
    return 0;
}