drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ Codeforces DP 区間分割型シーケンシャルDP 復元 考察：順序を工夫して解く 最適化の考察：変形しても悪化しない グルーピング(算数) グルーピングの最適化 算数と数学 CodeforcesDIV3 CodeforcesR2200 区間分割の仕方を走査する問題 最大値と最小値の差を扱う問題 DP 復元非本質＞＜ 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とする。 チーム分けの良さの最大値を求め、具体的な分け方も求めよ。 制約 考えたこと とりあえずソートしたくなる。ソート順に区間分割していくイメージで問題なさそう。ここまでは、いつもの、という感じ。区間分割を最適化する DP は基本的には、以下のような定義で になる。 dp[ i ] := 最初の i 個の要素をいくつかの区間に分割したときの最適値… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F04%2F07%2F032400" title="Codeforces Round #598 (Div. 3) E. Yet Another Division Into Teams (R2200) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2020-04-07 03:24:00 rich https://drken1215.hatenablog.com/entry/2020/04/07/032400 1.0 100%