コンテスト中AC:A〜C,E
E - Takahashi and Animals
グラフの問題として考えていたので、言い換えておきます。
頂点について、頂点
と頂点
の間には辺
があり、そのコストは
です。
ここから、以下の条件を満たすように辺をいくつか削除します。
- すべての頂点の次数が1以上
残った辺のコストの総和をスコアとする時、スコアの最小値を求めてください。
辺がある時とない時で状態が2通りしかないので、の小さい方から順にdpができないか考えます。
辺
の状態が
の時のスコアの最小値。但し、
の時、辺
は削除されている
の時、辺
は残っている
遷移について、辺番目が決定しているとして、辺
を考えます。
辺
を残す場合
辺は削除されていても残っていてもよいです。従って、
辺
を削除する場合
辺は残っている必要があります。そうしないと、頂点
の次数が0になります、従って、
このように遷移していけば解けるかのように思えますが、例えば、の時の初期値を
として、と更新していくと
で困ったことになります。というのも、
辺が存在する場合でも、辺
が存在しない場合には辺
を残さなければならず、前述の遷移通りいきません。
これを解決するためには辺が残っているかどうかの情報があれば良いので、DPテーブルに追加します。
辺
の状態が
であり、かつ、辺
の状態が
の時のスコアの最小値。但し、
の時、辺
は削除されている
の時、辺
は残っている
の時、辺
は削除されている
の時、辺
は残っている
遷移は、の両方の場合が必要になるだけで、先程と同じです。
辺を初期値とします。
としておきます。(は矛盾しており、あり得ない状況です。)
このDPをまで順に更新します。
辺の状態は、辺
の状態に従います。
辺のいずれか一方が削除されている場合
頂点の少なくとも一方は次数0なので、辺
は残す必要があります。よって、この時は、
辺の両方がある場合
頂点の両方とも次数が1なので、辺
は不要です。よって、この時は、
最終的な答えは、です。
提出コード