题解 P3724 【[AH2017/HNOI2017]大佬】

### Description 你现在要怼 $m$ 个大佬，第 $i$ 个大佬的自信值是 $C_i$ 。每次怼大佬之前，你的自信值是 $mc$，等级 $L=0$，嘲讽值 $F = 1$。对于每一个大佬，你都有 $n$ 天时间来怼大佬。无论哪个大佬，他们都会在第 $i$ 天使你的的自信值下降 $a_i$ 如果你的自信值为负数，那么你失败了。在第 $i$ 天，你可以干一下事情中的恰好一件： 1. 使得大佬自信值下降 $1$ 2. 使得自己的自信值增加 $w_i$ 3. 把自己的等级 $+1$ 4. 把自己的 $F$ 乘上 $L$ 5. 怼大佬，使得大佬的自信值下降 $F$，之后$L=0$ ，$F=1$ 如果中途大佬自信值为负数，你失败了。若大佬自信值恰好为 $0$ ，则你成功了。 对于每个大佬求你能否成功。 ### Solution 首先，可以发现，怼大佬和活下来两件事是互相独立的。并且怼大佬只与天数相关。显然天数越多越有可能。 所以先用一遍简单 dp 得出最多能剩下多少天来怼大佬并且保证自己活下来。设最多天数是 $D$ 。 然后用一遍 BFS 的出所有二元组 $(d, f)$ 表示用了 $d(<D)$ 天并且此时 $F = f$ 。注意去重。 你能怼死大佬有三种情况： 1. 不怼大佬。只执行 $1$ 操作。此时需要满足 $C_i \leq D$ 2. 只怼一次大佬。这时能怼死大佬需要满足存在一个二元组 $(d',f')$ 使得 $f' \leq C_i$ 并且 $f'+D - d \ge C_i$ （一次不能怼死，用 $1$ 操作耗死） 3. 怼两次。可以发现，若两次分别是 $(d_1,f_1), (d_2, f_2)$ 则类似于第二种情况，有 $f_1+f_2\leq C_i$ 并且 $f_1+f_2+(D-d_1-d_2) \ge C_i$ 。显然，对于一个 $f_i$ ，只有最小的那个 $d_i$ 才是最优的。所以我们对每个 $f$ 只保存最小的 $d$ ，并且按照 $f$ 排序。由于需要满足$f_1+f_2\leq C_i$， 就可以直接用双指针扫一遍，中途判断是否存在 $f_1+f_2+(D-d_1-d_2) \ge C_i$ 即可。 由于 $f$ 增长的很快，导致二元组不会特别多，于是可以通过此题。 ### Code [看代码戳这里](https://acfunction.github.io/2019/06/21/BZOJ4828/#Code)