ビットDP 超入門 PHP編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
step1 では集合をビット列で表す練習をしました。
次は、ビットDPと呼ばれる、集合をビット列で表した動的計画法を学んでいきます。
paiza 国には N 色の花があります。
花屋が M 個あり、店 i は色 C_i の花を P_i 円で売っています。
すべての色の花を 1 つ以上手に入れるのに必要な費用の最小値を求めてください。
ただし、すべてのテストケースにおいて、すべての色の花を 1 つ以上手に入れることが可能であると保証されます。
入力例 1 では、店 4, 5, 6 でそれぞれ色 2, 1, 3 の花を買うと 6 円ですべての色の花を 1 つ以上手に入れることができます。
5 円以下ですべての色の花を 1 つ以上手に入れることはできないので、6 を出力します。
入力例 2 のように、答えが 32 bit 整数に収まらない場合があることに注意してください。
この問題を動的計画法で解いてみましょう。
集合 S をいま手に入れた花の色の集合とします。
天下り的ですが、以下の配列を考えます。
dp[S] = 色 j (j ∈ S) の花を手に入れるのに必要な費用の最小値この配列を用いて動的計画法を考えてみましょう。
実装では、配列のインデックスに集合 S に対応するビット列を 2 進数とみたものを使えばよいです。
初期値は dp[0] = 0、問題の答えは dp[(下位 N ビットがすべて 1 のビット列)] です。
では、遷移はどうなるか考え、この問題を解いてください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N M
C_1 C_2 ... C_M
P_1 P_2 ... P_M
・ 1 行目には、花の色の数を表す整数 N と店の数を表す整数 M が空白区切りで与えられます。
・ 2 行目には、店 i で売っている花の色 C_i が空白区切りで与えられます。
・ 3 行目には、店 i で売っている花の価格 P_i が空白区切りで与えられます。
・ 入力は合計で 3 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
すべての色の花を 1 つ以上手に入れるのに必要な費用の最小値を求めてください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 14
・ N ≦ M ≦ 500
・ 1 ≦ C_i ≦ N
・ 1 ≦ P_i ≦ 10^9
・ すべての j (1 ≦ j ≦ N) に対して、j = C_i となる i が 1 つ以上存在する（すべての色の花を 1 つ以上手に入れることが可能である）
- 入力例1
-
3 7
1 2 3 2 1 3 3
9 8 6 1 3 2 11
- 出力例1
-
6
- 入力例2
-
6 6
1 2 3 4 5 6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
- 出力例2
-
6000000000
- 入力例3
-
14 20
1 4 5 9 7 8 10 4 2 6 5 7 11 1 8 13 12 14 3 12
748091032 923248344 306578263 901959268 881889099 131363705 631804792 192486880 859116 774415753 107366389 237889264 6749527 200817708 418364455 262808036 919218986 857841956 574646143 318335004
- 出力例3
-
5199343541
