求助数数题
  • 板块学术版
  • 楼主WZKQWQ
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/2/13 19:25
  • 上次更新2023/10/24 00:52:34
查看原帖
求助数数题
239433
WZKQWQ楼主2023/2/13 19:25

Rt,https://acm.timus.ru/problem.aspx?space=1&num=1387

题意是问n个点的有根树的数量(同构算一个)

我的做法是强制儿子从小到大,设dp_i_j表示儿子的子树大小和为i,每个儿子的子树大小至少为j的方案数,然后f_i为i个点的有根树的数量(同构算一个)。

转移就是dp[x][y] = dp[x][y] + f_i * dp_(x-i)_i

f_i = dp_(i-1)_1

问问为什么会算重,前面样例都能过

2023/2/13 19:25
加载中...