首页 > 至至子的公司排队
开通博客写题解
头像 an_da
发表于 2022-08-20 10:29:52
F 较好的观感 树上拓扑序计数|树形DP https://ac.nowcoder.com/acm/contest/38630/F 思路 每个公司是一棵树，然后每个公司可以看做连在一个虚拟的根上。每个公司的计算方案实际上就是计算这棵树的拓扑序的个数。用树形DP求解。 f[u]f[u]f[u] : 以u 展开全文
去ta的博客 赞 (10) 回复(1) 收起
头像 yukari1735
发表于 2022-08-22 20:44:40
树形 DP\text{DP}DP。 设以 uuu 为根的子树的答案为 fuf_ufu​，考虑如何合并两棵子树的答案。 假如我们有两个合法排队序列 A,BA,BA,B，长分别为 n,mn,mn,m，那么将这两个序列归并为 CCC，若在 CCC 中 A,BA,BA,B 中元素的相对顺序没有变化，那么 C 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客572538671号
发表于 2022-08-20 11:05:39
*******************欢迎探讨 未补：A：未补原因：赛时已过：无算法 未补：B：未补原因：赛时已过：无算法 未补：C：未补原因：赛时已过：无算法 未补：D：未补原因：赛时已过：无算法 未补：E：未补原因：赛时已过：模拟 补题：F：树形dp 小吐槽：树形dp，赛时没时间写(写了也不一定 展开全文
去ta的博客 赞 (1) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”