Codeforces 8VC Venture Cup 2016 - Elimination Round F. Group Projects
通した人のコードを眺めてたら大体何をしてるのか分かったので解説を書きます。
解法
配列はソートしておく。
次のようにグループ分けするのではなく、
次のようにグループ分けすると考えても imbalance は変わらない。
imbalance は図に書かれた値の総和である。
このことを用いると次のような DP ができる。
- dp[ i番目まで見た ][ j 個の区間が open ][ imbalance ] := この状態に至るパターン数
遷移パターンは open, close, pass, open and close の 4 通り。順に説明する。
open
close
どの区間を閉じるかで open 通りある。
pass
ai をどのグループに入れるかで open 通りある。
open and close
つまりグループに要素がひとつしかないとき。 imbalance は変化しない。
Codeforces 8VC Venture Cup 2016 - Elimination Roun ...
DP テーブルの置き方までは素直だけど imbalance の扱いが技巧的。