けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

最小カット:K値変数をK-1個の0-1変数で表す

AtCoder ABC 326 G - Unlock Achievement (橙色, 625 点)

2 変数劣モジュラ関数の和の最小化を最小カットにするやつ! 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…