题目;
给你一个长度为n的数组，每个位置上有一个野怪，野怪的攻击力和血量已知，你有m个技能，每个技能有三个值，一是可以击败的怪物，且怪物死后会攻击与它相邻的怪对于左边的怪伤害是血量-l，右边的怪时血量-r，如果大于该怪物的防御力即可击败这个怪物，问如何操作使得所有怪物至少被击败一次
题解:
- 首先对于杀死一个怪物,就会搞死一片人,
- 通过预处理得出这些区间, 怎么弄呢? 就直接当前目标的防御减去右边的或者左边的人的攻击
- 用st表存入最小值,在用二分答案搞出这个区间,
- 用线段树也可以搞定
- 现在问题就是 用这些区间来覆盖 1,N 的方案数
- DP解决, f[i] 表示 恰好覆盖 1,i 这个区间的方案数
- 整么更新捏?
- 首先将 这些区间 按照 r 升序来排, 然后在以l 位升序来排
- 对于 一个区间的贡献 就是
- dp[r]+ = ∑ dp[j] (j = [l−1 , r]) // 这里是到达 R ,很巧妙,仔细思考, 先是单个的加, 然后 就是 在前面的所有情况就一个当前情况,就可以表达所有情况了
0 ≤ i ≤ l − 2, dp[i] ∗= 2 , 当前区间 选不选 都无所谓,都可以,没有影响, 因为后面的区间值
初始化dp[0] = 1