AtCoder Beginner Contest 224
source link: http://www.shuizilong.com/house/archives/atcoder-beginner-contest-224/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
在这里输入要转换的内容- 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.。。那么就是最小覆盖集。。所以大概可以上费用流。。
事实上也确实是费用流，建模需要使用线性规划对偶。。。
应该是最简单的线性规划对偶模型。。。
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK