054D
AGC054D (ox)
有点厉害题。对于括号序列和序列上邻项交换的问题的处理有一些启发。 首先考虑如果没有 ox 怎么样。容易发现,我们从前往后记录左括号与右括号的个数差,这个差值一旦为负就立刻从后面提一个右括号过来(一路交换过来),这个做法一定是最优的,并且是唯一最优的操作方法。这样理解比较感性,实际上我们可以对每个分界 ......
题解 AGC054D
## 前言 因为本人尚菜,所以本篇文章没有什么数学符号,请大家放心食用。 ## 题目分析 先吐槽一嘴,这个 `o` 表示 `()`,这个 `x` 表示 `)(`,十分形象。 好,我们先观察原序列,容易得出第一条性质: > `ox` 的加入不会让我们不合法的序列变合法,相反,它会让我们合法的序列变不合 ......
abc054d <dp, 背包>
https://atcoder.jp/contests/abc054/tasks/abc054_d ``` // https://atcoder.jp/contests/abc054/tasks/abc054_d // 背包 // 这里开始的时候数据规模想错了, 所以用了map, 实际上可以用数组 ......