個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ!
問題概要
個の宝箱がある。宝箱を開けるための鍵が 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵 を用いるのに だけコストがかかり、それを用いることで対応している宝箱がすべて開く (すでに開いている宝箱は変化しない)。
最終的にすべての宝箱を開けるのに必要な最小コストを求めよ。
制約
考えたこと
見るからに bitDP!!!
bitDP は「ある集合の部分集合を添字とした DP」ができる!!!
今回の DP は
- dp[ i ][ S ] := 最初の i 個の鍵からいくつか選んで、開いた宝箱の集合が S で表されるような場合についての、最小コスト
という感じでうまくいく。集合 S はビットで表すのが便利で、たとえば のときは
- S = 0 ( { } )
- S = 1 ( {0} )
- S = 2 ( {1} )
- S = 3 ({1, 0} )
- S = 4 ( {2} )
- S = 5 ( {2, 0} )
- S = 6 ( {2, 1} )
- S = 7 ( {2, 1, 0} )
という 23 = 8 通りの値をとる。宝箱が 個なら、S は の 通りの値をとる。
bitDP の更新
部分集合をビットで表す考え方については、以下の記事にまとめた。
今回必要になる知識は
- 集合 S (に対応するビットは s) と集合 T (に対応するビットは t) に対して
- S と T の和集合 S T は a | b で表せる
という感じ。これからナップサック DP と同様に、 dp[ i ][ s ] () の値がわかってることを前提として、dp[ i + 1 ][ s ] () の値を更新していく。ナップサックでは s の部分は「ナップサックにすでに入っている品物の重さの合計値」だったが、今回は「すでに開いている宝箱の部分集合」である。
i 番目の鍵を使わないとき
単純に
- chmin(dp[ i + 1 ][ s ], dp[ i ][ s ])
となる。chmin についてはここを参照。
i 番目の鍵を使うとき
i 番目の鍵に対応している宝箱の集合をビット c[ i ] で表すことにすると、
- chmin(dp[ i + 1 ][ s | c[ i ] ], dp[ i ][ s ] + a [ i ])
となる。
初期条件
初期条件は単純に
- dp[ 0 ][ 0 ] = 0 (それ以外のところは INF に初期化)
で OK
計算量
計算量は で十分間に合う。
#include <iostream> #include <vector> #include <algorithm> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } const long long INF = 1LL<<60; int N, M; vector<long long> a, b; vector<int> c; long long dp[1100][5000]; int main() { int N, M; cin >> N >> M; vector<long long> a(M), b(M), c(M, 0); // c はビットで表す for (int i = 0; i < M; ++i) { cin >> a[i] >> b[i]; for (int j = 0; j < b[i]; ++j){ int t; cin >> t; --t; c[i] += (1<<t); } } for (int i = 0; i < 1100; ++i) for (int j = 0; j < 5000; ++j) dp[i][j] = INF; dp[0][0] = 0; for (int i = 0; i < M; ++i) { for (int j = 0; j < (1<<N); ++j) { chmin(dp[i+1][j], dp[i][j]); int nj = j | c[i]; chmin(dp[i+1][j | c[i]], dp[i][j] + a[i]); } } cout << (dp[M][(1<<N)-1] < INF ? dp[M][(1<<N)-1] : -1) << endl; }