2020-2021:teams:hotpot:codeforces666div1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:codeforces666div1 [2020/09/04 09:57] 喝西北风 创建 |
2020-2021:teams:hotpot:codeforces666div1 [2020/09/04 22:15] (当前版本) 喝西北风 [题解] |
||
|---|---|---|---|
| 行 26: | 行 26: | ||
| 若存在一堆石子大于其余所有石子之和，则先手胜。否则石子总数之和为奇数则先手胜，为偶数则后手胜。 | 若存在一堆石子大于其余所有石子之和，则先手胜。否则石子总数之和为奇数则先手胜，为偶数则后手胜。 | ||
| + | |||
| + | =====C - Rainbow Rectangles===== | ||
| + | |||
| + | ====题意==== | ||
| + | |||
| + | n层塔，每层有$a_i$个小怪和一个大怪。小怪有一滴血，大怪两滴血。在一层有三种操作。第一是$r_1$的代价打一个怪1滴血，第二是$r_2$的代价打所有怪1滴血，第三是$r_3$秒杀一个怪。上一层或下一层需要花费d。如果对大怪造成了伤害却没有杀死大怪，则强制立即上一层或下一层（需要花费d）。一开始在第一层。问杀死所有怪的最小花费。 | ||
| + | |||
| + | ====限制==== | ||
| + | |||
| + | $1\le n \le 10^6$,$1\le r_1 \le r_2 \le r_3$ | ||
| + | |||
| + | ====题解==== | ||
| + | |||
| + | 最优策略下，不会连续下两层（因为上二下二上二和上一下一上二下一上一是一样的）。因此可以用dp1[i]表示第i层怪全部杀死，当前在第i+1层的最小花费，dp2[i]表示第i层还剩一滴血大怪，当前在第i+1层的最小花费。转移比较复杂，但不是很难推。注意只推到dp[n-1]，最后一层和之前情况不太一样。 | ||
2020-2021/teams/hotpot/codeforces666div1.1599184641.txt.gz · 最后更改: 2020/09/04 09:57 由 喝西北风
