問題 長さの数列[A_1, \cdots, A__N]から個の要素を選んで部分数列を作る。 要素を選ぶときは、要素ごとに以上開ける必要がある。 辞書順で最小の数列を求める。 考察 のとき、部分列を作ることはできない。 以下、を仮定する。 同じ数字が複数あり、どちら…

問題 個の敷地（番目の敷地の範囲は、コストは）がある。 座標にあるビルのコストは、その座標を含む敷地のコストの和。 軒のビルのコストを求める。 atcoder.jp 考察 考える平面が広いので、座標圧縮を行う。 以降、圧縮後の座標で考える。 あるビルのコス…

問題 王国に個の街がある。 魔王が番目の街にモンスターを匹送ると、王国にのダメージを与える。 魔王は個の拠点があり、合計のモンスターを番目の街に好きな配分で送り込める。 王国に与えられダメージの最大値を求める。 atcoder.jp 考察 次のようなdpを考…