[AtCoder] ABC 119 C – Synthetic Kadomatsu

Synthetic Kadomatsu

https://atcoder.jp/contests/abc119/tasks/abc119_c

考え方

題意

長さ \( A, B, C \) の竹を作るために必要な最小のコストを求めます。

方針

ある長さの竹を作るためには一つ以上の竹を使う必要があることに注意します。

竹\( 1, 2, 3 \) を \( A, B, C \) の長さにすることを考えます。このとき、竹\( 1, 2, 3 \) の長さは \( 0 \) とします。これらに対して \( N \) 本の竹の合成の仕方を考えると、長さ \( l_i \) の竹を 竹\(1, 2, 3 \) に合成する又はどの竹にも合成しないの \( 4 \) 通りあることが分かります。

したがって、全体で \( 4^N\) 通りありますが、長さ \( 0 \) の竹は除外しなければいけません。  また、合成を行うたびにコストが \( 10 \) 増えます。

深さ優先探索によって全探索を行うときに必要な値は、現在の竹 \( 1, 2, 3 \) の長さ、コスト、全体で何本竹まで調べたかです。\( N \) 本の竹まで探査を終えたときの各竹の長さを \( a, b, c \) と合成した回数を \( k \) とすると、求める全体のコストは、

\[ |A – a| + |B – b| + |C – c| + 10k – 30\]

となります。

なぜ \( -30 \) となっているかというと、長さ \( 0 \) の竹に合成するコストは必要なく、この合成が必ず \( 3 \) 回行われるからです。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする