思路
考虑树形 \(\text{dp}\)。
我们将每个人与把自己淘汰的人连边。
得到一颗以一为根的树。
由于我们需要求出必须赢的场数最多的那位选手，至少要赢多少场。
考虑最多的限制。
可以使用树型动态规划。
每一次两个人比赛的代价为：
\[dp_i=\max(dp_i,dp_j)+1
\]
这样就达成了最多的限制。
考虑至少的条件。
我们容易发现其中一项一直都是 \(dp_i\)。
那么我们容易想到将 \(dp_j\) 从小到大排序，就完成了最少的条件。
[AGC009B] Tournament 题解
发布时间 2023-10-13 21:54:41作者: Al_lA