ビットDP 入門 PHP編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
step2 では、ビットDPと呼ばれる集合をビット列で表した動的計画法を学びました。
最後に step2 より難しいビットDPを解いてみましょう。
paiza 国には N 色の花があります。
花屋が M 個あり、店 i は色 C_{i,1}, C_{i,2}, ... , C_{i,k_i} の花をセットで P_i 円で売っています。
すべての色の花を 1 つ以上手に入れるのに必要な費用の最小値を求めてください。
ただし、すべてのテストケースにおいて、すべての色の花を 1 つ以上手に入れることが可能であると保証されます。
入力例 1 では、店 3, 5 で花のセットを買うと 20 円ですべての色の花を 1 つ以上手に入れることができます。
19 円以下ですべての色の花を 1 つ以上手に入れることはできないので、20 を出力します。
step2 と同じように動的計画法を考えます。
配列を dp[S] = 色 i (i ∈ S) の花を手に入れるのに必要な費用の最小値 と定義することや、初期値や問題の答えは step2 と同じでよいです。
しかし、今回は花がセットで売られています。
そのため、step2 とは遷移が少し異なります。
どのように遷移すればよいか考えてみましょう。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N M
k_1 C_{1,1} C_{1,2} ... C_{1,k_1}
k_2 C_{2,1} C_{2,2} ... C_{1,k_2}
...
k_M C_{M,1} C_{M,2} ... C_{M,k_M}
P_1 P_2 ... P_M
・ 1 行目には、花の色の数を表す整数 N と店の数を表す整数 M が空白区切りで与えられます。
・ 続く M 行には、店 i で売っている花のセットに含まれる花の色の種類数 k_i とセットに含まれる花の色 C_{i,j} は空白区切りで与えられます。
・ 3 行目には、店 i で売っている花のセットの価格 P_i が空白区切りで与えられます。
・ 入力は合計で 2 + M 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
すべての色の花を 1 つ以上手に入れるのに必要な費用の最小値を求めてください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 14
・ N ≦ M ≦ 500
・ 1 ≦ k_i ≦ N
・ 1 ≦ C_{i,1} < C_{i,2} < ... < C_{i,k_i} ≦ N
・ 1 ≦ P_i ≦ 10^9
・ すべての j (1 ≦ j ≦ N) に対して、j = C_{i,l} となる i が 1 つ以上存在する（すべての色の花を 1 つ以上手に入れることが可能である）
- 入力例1
-
3 5
1 3
2 1 3
2 2 3
3 1 2 3
1 1
10 12 12 30 8
- 出力例1
-
20
- 入力例2
-
5 5
3 1 2 3
2 1 5
1 2
1 4
3 2 3 5
1000000000 1000000000 1000000000 1000000000 1000000000
- 出力例2
-
3000000000
- 入力例3
-
14 20
3 1 2 5
3 5 9 11
7 2 7 9 10 12 13 14
12 1 3 4 5 7 8 9 10 11 12 13 14
13 1 2 3 4 6 7 8 9 10 11 12 13 14
4 2 6 8 13
2 10 13
10 1 3 4 5 6 7 9 10 11 12
5 2 3 6 11 12
3 2 7 12
13 1 2 3 4 5 7 8 9 10 11 12 13 14
7 1 5 6 8 9 10 12
7 1 2 3 4 6 10 12
10 1 2 4 6 8 9 10 11 13 14
8 4 5 6 7 8 9 11 12
8 2 4 5 8 9 10 12 13
3 2 3 6
11 1 2 4 5 6 7 8 10 11 12 14
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14
8 4 5 6 7 8 9 10 12
590283977 89275030 949651125 237286753 547920963 930967542 373333931 136902062 109857646 554589667 137858778 675355649 563258296 806703489 809035940 934029347 514245071 107149658 405528662 792940859
- 出力例3
-
245008436
