ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Longest Increasing Subsequence (LIS)

Educational DP Contest / DP まとめコンテスト Q - Flowers

問題 提出コード 解法 とりあえず、最終的に残る花は、かつを満たすので、LISっぽいことを考えてみます。 一番高さが高い(つまり右端)花の番号がになるような並べ方の中での、美しさの総和の最大値 とします。 すると、次のような操作を、が小さい方から行え…

Typical DP Contest K - ターゲット

問題 提出コード 解法 区間スケジューリングのように、区間の終わりの部分に注目すると、LISに帰着させることができます。 まず、中心座標はx軸上に存在しているので、それぞれの円について、中心座標とがわかっているとき、円と軸が接する2点は、とになりま…

ABC006 D - トランプ挿入ソート

問題 提出コード 解法 基本的に、1つのトランプは1回操作するだけで必ず正しい位置に戻せるので、最悪N回の操作が必要になります。 そして、操作の回数を最小にするには、そもそも操作しないトランプの枚数を最大化すればいいことになります。 これはつまり…