树形dp题单
[COCI2009 Final Exam#1] PODJELA¶
题目描述
有 \(n\) 个农民，他们住在 \(n\) 个不同的村子里，这 \(n\) 个村子形成一棵树，每个农民初始时有 \(x\) 元钱。 每一次操作，一个农民可以从它自己的钱中，取出任意数量的钱，交给某个相邻村子的农民。 对于每个农民给定一个值 \(v_i\)，求最少需要多少次操作，使得每个农民最终拿到的钱 \(\geq\) 给定的值。
输入格式
第一行包含一个整数 \(n\) ，即农民数。 第二行包含一个整数 \(x\) ，即每个农民初始时拥有的钱数。 第三行包含 \(n\) 个整数，第 \(i\) 个数表示 \(v_i\) 。 接下来 \(n-1\) 行每行包含两个整数, 表示树上的一条边。
输出格式
输出一行一个整数, 即最少需要的操作次数。
对于 \(100\%\) 的数据，\(1 \leq n \leq 2000,~0 \leq x \leq 10000,~\sum\limits_{i=1}^{n}v_i \leq n\times x\)
首先将点权变为x-v_i。于是最后的目标就是使得所有点的点权非负
那么设f_{i,j}为对i子树进行j次操作后，在子树i中的点权全部合法（除了i可以为负数）的前提下，i的点权的最大值。
最后的答案就是最小的j使得f_{1,j}≥0。
实现起来的细节比较多。
Win¶
题目描述
win 世界乒乓球比赛马上要拉开帷幕，你被邀请成为组委会成员，并且负责安排比赛赛程。
比赛采取淘汰赛赛制，失败的一方将被直接淘汰。
你手上现在有一份各个队员近期的战况，战况包含任意两名队员的最近一次交手结果，你默认这份对战结果将代表比赛的结果。
现在，你的好友要参加乒乓球比赛，你需要帮好友算一下，你可以安排出多少种淘汰赛赛程使得你的这位好友能够拿到最终的冠军。
当然，介于比赛的公平性，赛程的安排需要遵循这个原则，那就是使得淘汰赛的赛程树高度最低，也就是说，使得每位选手打的比赛数尽量平均。
输入格式
本题多测。
每组数据第一行有两个整数 n,m，表示总共有 n 位选手参加比赛，你的好友编号为 m。
接下来一个 n×n 的矩阵，表示选手两两间交手的胜负。
其中第 i 行，第 j 列的数 ai,j 表示其胜负关系，并且满足 ai,j∈{0,1}，ai,j+aj,i=1，ai,i=0。
ai,j 为 1 表示 i 胜过 j，ai,j 为 0 表示 i 输过 j。
请输入直到文件底结束。