某島

… : "…アッカリ~ン . .. . " .. .
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.。。那麼就是最小覆蓋集。。所以大概可以上費用流。。

事實上也確實是費用流,建模需要使用線性規劃對偶。。。
應該是最簡單的線性規劃對偶模型。。。