[LgP1472]奶牛家谱

OI 题解 DP

算法：DP

这个题显然是一个dp，我们考虑一棵树，深度为d，大小为s，可以把它分成三部分：根节点，左子树，右子树。而且，两个子树中必有一个深度为d-1，而且，我们可以看到，当左右子树只有一棵深度为d-1时，是对称的，所以，我们可以推出：

$$f[s][d] = sum\{f[k][d-1] * sum\{f[s-k-1][l]|0<l<i-1\}*2+f[k][d-1] *f[s-k-1][d-1]|0<k<s-1\}$$

但是，这还是太慢了！
仔细观察我们可以发现，内层的sum可以用前缀和优化！
所以：

$$f[s][d] = sum\{f[k][d-1] * g[s-k-1][i-2]*2+f[k][d-1] *f[s-k-1][d-1]|0<k<s-1\}$$

这样就可以过了！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 200 + 5, K = 100 + 5, MOD = 9901;
int f[K][N], g[K][N], n, k;
int main() {
    cin >> n >> k;
    f[1][1] = 1;
    for(int i = 1; i <= k; ++ i) {
        g[i][1] = 1;
    }
    int s;
    for(int i = 2; i <= k; ++ i) {
        s = (1 << i) - 1;
        for(int j = 3; j <= n; ++ j) {
            for(int l = j - 1; l > 0; -- l) {
//              for(int d = 1; d < i - 1; ++ d) {
//                  f[i][j] = (f[i][j] + f[i - 1][l] * f[d][j - l - 1] * 2 % MOD) % MOD ;
//              }
                f[i][j] = (f[i][j] + f[i - 1][l] * g[i - 2][j - l - 1] * 2 % MOD) % MOD;
                f[i][j] = (f[i][j] + f[i - 1][l] * f[i - 1][j - l - 1] % MOD) % MOD;
            }
            g[i][j] = (g[i - 1][j] + f[i][j]) % MOD;
        }
    }
    cout << f[k][n] << endl;
    return 0;
}