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

发表于 | 分类于

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

链接

UVa 1362

题解

书上的解法，用 表示欧拉序列 中的第 到第 个字符所表示的树的数量，则有：

  1. 当 时，；
  2. 当 时，，因为欧拉序列的第一个点和最后一个点都必须是根节点。

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

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

代码

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