BZOJ 3754 最小方差生成树
BZOJ 3757 苹果树

SPOJ 8549 BST again

zimpha posted @ Tue, 25 Nov 2014 11:24:01 +0800 in acmicpc , 594 readers

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;
}
  • No match

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter