OI

CF2133D 题解

0 条评论 OI 无标签 SunJude
Solution首先考虑最简单的情况，每次只杀栈底的怪物：对于第 $1$ 个怪：需要 $h_1$ 刀。对于第 $i(i \geq 2)$ 个怪：在第 $i - 1$ 个怪死后，它会掉 $1$ 点坠落伤害，于是就需要 $\max(0, h_i - 1)$ 刀。此时的答案是 $\textrm{base} = h_1 + \sum_{i = 2} ^{n} \max(0, h_i - 1)$。然后...

UVA1626 题解 / test

0 条评论 OI 无标签 SunJude
Solution采用 区间 dp。对于串 $s$，$f_{l,r}$ 表示使 $[l,r]$ 区间变为正规括号序列所需添加的最少括号数量。初始化：$l = r$ 时，区间 $[l,r]$ 中只有一个括号，添加一个与之匹配的括号即可，故 $f_{l,r} = 1$。$l > r$ 时，不存在这种情况，$f_{l,r} = 0$。$l < r$ 时，由于需取最小值，故 $f_{l,r...