きろく

特筆すべき記録のまとめ

Educational DP Contest:L - Deque

問題

atcoder.jp

解法

dp(i, j, k) := 数列 a_i ~ a_j の中で k が操作するときの (X, Y) の値

と定義する.このとき,

dp(i, j, k) = ( dp(i + 1, j, (k + 1) % 2).X + a_i, dp(i + 1, j, (k + 1) % 2).Y ) か ( dp(i, j - 1, (k + 1) % 2).X + a_j, dp(i, j - 1, (k + 1) % 2).Y ) のうち最適なもの (k が太郎のとき)

dp(i, j, k) = ( dp(i + 1, j, (k + 1) % 2).X, dp(i + 1, j, (k + 1) % 2).Y + a_i ) か ( dp(i, j - 1, (k + 1) % 2).X, dp(i, j - 1, (k + 1) % 2).Y + a_j ) のうち最適なもの (k が次郎のとき)

dp(i, j, k) = (0, 0) (j < i のとき)

と漸化式が立つ.状態数 O(N^2),遷移 O(1) となり O(N^2).

解答

atcoder.jp

dp の値を std::pair<LL, LL> とおいたので重くなった.

f:id:babcs2035:20190107172221p:plain