AtCoder Educational DP (WXYZ)

這些 DP 題中有些基礎的模型和優化。做做玩玩順便複習一下一些基本的東西。

感覺好像沒怎麼能搜到幾個最後幾題的題解啊（盡管這幾題還是很簡單）

給定一個序列 \(h\)，從 \(i\) 跳到 \(j\) 的代價為 \(C+(h_j-h_i)^2\)。求 \(1\) 到 \(n\) 的最小代價。

\(f_i\) 表示到 \(i\) 的最小代價，則有

\[f_i=C+\min_{j<i} f_j+(h_i-h_j)^2\\

f_i=C+h_i^2+\min_{j<i} (f_j+h_j^2)-2h_ih_j\\

\]

轉移即用 \(2h_i\) 的線去切由 \((h_j,f_j+h_j^2)\) 組成的下凸殼。一開始并沒有看到 h 已經排序，還寫了一半 cdq，然而單調隊列即可。

https://atcoder.jp/contests/dp/submissions/27010220

一個網格圖，其中包含 \(n\) 個障礙點，問不經過障礙點到 \((H,W)\) 的方案數。

經典容斥題。

把障礙點和終點都設為關鍵點。把所有關鍵點按照拓撲序排序（此題就是按 \(x\) 排序）。設 \(f(i,j)\) 表示從第 \(i\) 個關鍵點到第 \(j\) 個關鍵點的不考慮阻礙的方案數，易知 \(f_{i,j}=\binom{x_j+y_j-x_i-x_i}{x_j-x_i}\)。考慮設 \(g_i\) 表示從初始節點到第 \(i\) 個關鍵點，除去這個關鍵點其他障礙全部沒有經過的方案數，則有 \(g_i=\binom{x_i+y_i-2}{x_i-1}-\sum_{j<i} g_jf_{j,i}\)。

選出一些數，然後排列一下，使得對于任意 \(x\) 滿足它前面的 \(w\) 之和要小于等于 \(s_x\)。最大化選出來的價值和。

肯定要先貪心一下。可以推出按照 \(s+w\) 排序最優（考慮對于相鄰兩個放哪個更優）。

然後背包一下就可以啦。

https://atcoder.jp/contests/dp/submissions/27017190

有 \(n\) 個條件，每個條件給定一段區間和一個價值（可正可負），如果這段區間中存在 \(1\) 那麼就會讓總價值加上這個價值。問總價值最大的一個 \(01\) 序列。

考慮設 \(f(i,j)\) 表示對于前 \(i\) 個數，最後一個取的數為 \(j\) 的最大價值。轉移有兩種：取 \(i\) 和不取 \(i\)。也就是說這兩種分别為 \(f_{i-1,j}\to f_{i,j}\) 和 \(f_{i-1,j}\to f_{i,i}\)。這是可以用線段樹維護的。

具體而言，首先處理第二種更新。求出一個全局的最大值後，将 \(f_{i,i}\) 與其取 \(\max\)。然後考慮題目中的得分的貢獻。找到所有形如 \([l,i]\) 的區間，然後線段樹上 \(f_i(l,i)\) 全部加上這段貢獻即可。相當于一個區間更新區間查詢。

https://atcoder.jp/contests/dp/submissions/27018962

剩下的題基本都是沒有任何特點的簡單DP了。就懶得打了。