普及组套题.可能就 $AK$ 了.
- 前两题很 $sb$ ,没啥可说的.
- 考后发现 $T3$ 是个普及组模拟赛的题?还是入门 $OJ$ 上的… Link
- 考试做法:考虑枚举答案为 $t$ ,那么前 $t$ 天不割的总长是确定的,为 $\sum h_i+t\cdot grow_i$ .需要最大化 $t$ 次割草割去的长度总和.
- 一株草显然可以只割一次,割多次和只割最后一次是等价的.那么枚举范围就可以设为 $1\sim n$ .
- 而同一天也不能割两株草.所以 $n$ 株草, $t$ 天就形成了一个 $n\times t$ 的矩阵,每个点有权值,现在每一行每一列最多选 $1$ 个,要求共选 $t$ 个的最大收益,就成了经典模型.
用一个大数 $inf$ 减去原权值作为权值,就是最小费用最大流,最后算一下就可以了.由于 $n\leq 50$ ,肯定能过.
大家的做法:枚举答案 $t$ ,将草按 $grow$ 排序,先割 $grow$ 小的,再割大的,总共割 $t$ 次.
- 然后设 $f(i,j)$ 表示前 $i$ 株草割了 $j$ 株能获得的最大收益就好了.
- 贪心部分的正确性可以用经典套路证明,尝试交换两株草被割的次序,答案不会变得更优.
顿时感觉自己好 $sb$ 啊.如果这题把数据出大点今天可能就凉了…