某岛

… : "…アッカリ~ン . .. . " .. .
October 27, 2021

AtCoder Beginner Contest 224

在这里输入要转换的内容- https://atcoder.jp/contests/abc224/tasks

E. Integers on Grid

类似经典的 POJ 1088. 滑雪。。
不过状态是稀疏的。。用高度划分阶段,维护一下每一行每一列前阶段的最优解,转移就可以优化到 O(1) 了。

F. Problem where +s Separate Digits

给定一个数字串,可以在中间添加若干 + 号,
问所有可能的表达式的和是多少。

比赛时我的做法是,先枚举最后一个加号的位置,写出暴力的 O(n2) dp。。。
然后仔细观察,把转移也优化成 O(1)。。。。

题解给出的方法是,类比期望的线性性。。。去枚举每个字符的贡献。。比上面的做法要好写。。。。

G. Roll or Increment

是非常有趣的题。。让我想起了 PE. 503..
说有一枚骰子。。投掷完之后可以 d*A 的代价让数字 +d,或者 B 的代价重新投一次..
问第一次投出 s 时,期望最少多少代价得到 t

显然大于 s 的话一定要重新投,否则要么重新投,要么加。。
和 PE 503 类似。。这个决策的分割点也是具有单调性的。。。
(准确的说。。这个题里是凸性。。所以可以三分决策分割点。。。这样就可以通过了)
(然后和 PE 503 一样。。这两个题的决策分割点。。其实都是可以 O(1) 算出来的。。不过我都不会)

H. Security Camera 2

最后一题说给定一个二分图。。给定每个节点权值 +1 的代价。。。
然后对于所有的边。。要求连结两个点的权值和大于边权。。求最小代价。。
如果边权是 1.。。那么就是最小覆盖集。。所以大概可以上费用流。。

事实上也确实是费用流,建模需要使用线性规划对偶。。。
应该是最简单的线性规划对偶模型。。。