题解 CF1107F 【Vasya and Endless Credits】

2019-02-04 22:11:16


这题有DP的做法?然而我不会。


一天只能选一种方案,考虑二分图最大权匹配。

考虑天数向方案匹配。显然,第 $n-i+1$ 天选第 $j$ 种方案的收益为 $a[j]-b[j]*\min(i-1,k[j])$ 。

然后跑最大费用最大流或者 $\texttt{KM}$ 就行了。

注意到如果收益为负,还不如不选。于是只要在收益为负时强制把收益置成 $0$ 就行了。

然后,因为我常数大,费用流 $\texttt{TLE on \#5}$ , $\texttt{KM TLE on \#29}$ 。

于是我偷税地抄了官方题解,然而并不需要强制收益为 $0$ 。

但是普通的 $\texttt{KM}$ 好像还是需要的。


各种方法的代码见blog