Monge性
Codeforces
DP
グリッド
DP高速化
Monge性
「総和=K」を扱う
単調性に着目する
数列
高速畳み込み計算
解を変形していく(最適性を失わずに)
戻すDP
分割統治法
N個のものうち1個を変更・削除したものを解く
ナップサックDP
部分和
CodeforcesDIV1-D
CodeforcesR2800
から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…
Codeforces
数列
二値パラメータ問題
ConvexHullTrick
DP
分割統治法
DP高速化:MonotoneMinima
DP高速化
区間分割型ナップサックDP
誤差
オーバーフロー
Monge性
CodeforcesDIV1-C
CodeforcesR2400
sky さんの Monotone Minimma の例題!!! 練習として解いてみた。 問題へのリンク 問題概要 (意訳) 個の値の組 , が与えられる。 で であり、 は狭義単調増加、 は狭義単調減少である。 を適切に定めたときのスコアが、 で与えられる。スコアの最小値を求…