SPOJ 8549 BST again

BZOJ新挂的题，貌似数据范围比SPOJ上多了一点，但是算法本质没有任何变化，还是一个简单的dp。

题目大意

给你\(n,h\)，问有多少棵\(n\)个节点高度为\(h\)的二叉搜索树（标号为\(1\dots n\)，只有一个节点的树高为0），答案对\(10^9+7\)取模

数据规模：\(1 \le n, h \le 600\)

题目分析

我们有一个很直观的dp思路，设\(dp_{n,h}\)表示\(n\)个节点，高度为\(h\)的方案数，然后枚举一个数作为根节点进行转移，但是我们会发现转移方程列不出来，主要是某个分支的高度可能不够\(h\)。

既然恰好不可做，我们放宽条件，设\(dp_{n,h}\)表示\(n\)个节点，最多为\(h\)的方案数。类似的枚举\(i\)为根，我们可以得到如下方程\[dp_{n,h}=\sum_{i=1}^{n}{dp_{i-1,h-1}\cdot dp_{n-i,h-1}}\]

然后写个记忆化就搞定了，答案就是\(dp_{n,h}-dp_{n,h-1}\)。

时间复杂度\(O(n^2h)\)。

贴个代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 600 + 10, MOD = 1e9 + 7;
int dp[MAXN][MAXN];

int solve(int n, int h) {
    if (h < 0) return 0;
    if (dp[n][h] != -1) return dp[n][h];
    if (n == 0) return dp[n][h] = 1;
    dp[n][h] = 0;
    for (int i = 1; i <= n; ++ i) {
        dp[n][h] += (LL)solve(i - 1, h - 1) * solve(n - i, h - 1) % MOD;
        dp[n][h] %= MOD;
    }
    return dp[n][h];
}

int main() {
    int T; scanf("%d", &T);
    memset(dp, -1, sizeof(dp));
    while (T --) {
        int n, h; scanf("%d%d", &n, &h); ++ h;
        printf("%d\n", (solve(n, h) - solve(n, h - 1) + MOD) % MOD);
    }
    return 0;
}

• Relative Posts