题目:https://www.luogu.org/problemnew/show/P1472
真是道好dp
考虑:令f[i][j]为深度为i,节点数为j的树的方案
考虑分治,即这一颗树可以分为左右两个子树(当j = 1例外),可以分给左
子树k(k < j)个节点,这时根节点需要消耗一个点,所以分给右子树j - k - 1个节点
f[i][j] += f[i - 1][j - k - 1] * f[i - 1][k]
显然j不可能为偶数,所以枚举的时候枚举奇数即可
但稍等!还有一个问题,例如f[3][5] += f[2][1] * f[2][3],这时f[2][1]是0,但实际上这样的方案是存在的
因此我们要改变状态,将f[i][j]表示为深度不超过i,个数为j的树的方案
这时f[i][1]初始化为1,且最后统计答案是f[k][n] - f[k - 1][n](这样能统计出深度恰好为k的方案树)
以上
代码:
#include#include #include #include #include using namespace std;const int mod = 9901;const int maxn = 205;typedef long long ll;inline int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op;}int f[maxn][maxn];int main(){ int n = read(),k = read(); for(int i = 1;i <= k;i++) f[i][1] = 1; f[1][1] = 1; for(int i = 2;i <= k;i++) for(int j = 3;j <= n;j += 2) for(int k = 1;k < j;k += 2) (f[i][j] += f[i - 1][k] * f[i - 1][j - k - 1]) %= mod; printf("%d",(f[k][n] - f[k - 1][n] + mod)% mod);}