Codeforces 580D. Kefa and Diches

こどふぉす

問題

N種の料理からM種を順番に選んで食べる。
このとき、各料理自体の満足度の他に、料理iの直後に料理jを食べた場合の追加満足度もある。
満足度の最大値を求める。


1<=m<=n<=18
0<=k<=n*(n-1)
0<=満足度<=10^9

考え方

N種からM種選んで、その順番を列挙する方法だと、O(2^18 * 18!)で間に合わない。
選ばれたM種から最大となるような順序を効率的に求めることを考える。


これは、今まで食べた料理の情報と最後に食べた料理のbitDPで考えられるので、
dp[今まで食べた料理][最後に食べた料理]:=満足度の最大値
で更新すればよい。


さらに、NからMを選ぶ組み合わせとbitDPを分けて考える必要はなく、全部の料理でのbitDPでM個以下のものだけを使えばよいので、O(2^18 * 18 * 18)で済む。