ABC142 E - Get Everything
April 17, 2020
問題
考えたこと
問題の感じでDPかなと見える
どういうDPを組むかになってくる。こういうのは制約を見ると見えてくる
N < 12, M < 10^3なので、DP[M][M]みたいな2次元DPも考えれるし、Nが12なのでbit全探索も見える2^12 = 4096
bit全探索がちょうど良さそうな制約なので、それをうまく使えないか考えてみる
N=5だとして、1つ目の鍵で1,3,5, 2つ目の鍵で2,4,5, 3つ目の鍵で1,4の宝箱が開けれるとする
これを2進数で状態表してみると
初期状態だと -> 00000
1つ目の鍵を使うと -> 10101
1つ目使わず、2つ目だけを使う -> 01011
1つ目と2つ目を使う -> 11111
3つ目だけを使うと -> 10010
1つ目と3つ目を使うと -> 10111
2つ目と3つ目を使うと -> 11011
全て使うと -> 11111
これをみると、各状態を作るのに最小費用で作れるってのが表現できそうDP[x][y], x < M, y < 2^nとして
先頭からx番目までの鍵だけを使うときに, 状態をyとするのに必要な最小コストというのでできそう
bit操作系
i番目の鍵で開けれる状態の10進数表記
先ほどの考察で, 5個の宝箱があって1,3,5が開けれる鍵がある場合は10101と書いた
これを10進数表記に直すと1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 + 1*2^4で計算できる
プログラム的には下
rep(j, c[i].size()) {
num += pow(2, c[i][j]-1);
}
10101の状態から、2と5の宝箱を開けれる鍵を使った場合の状態の計算
i-1番目までの鍵で10101という状態ができるとして、i番目の鍵で2,5の宝箱が開けれるとすると
状態は11101となるが、これを簡単に10進数表記で得るには、bit演算のORでできる
C++でのORは|なので以下のようにできる
int state = bit | num;
提出したコード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
int n, m; cin >> n >> m;
vector<vector<int>> c(m, vector<int>());
vector<int> a(m);
rep(i, m) {
int b; cin >> a[i] >> b;
rep(j, b) {
int t; cin >> t;
c[i].push_back(t);
}
}
vector<vector<int>> dp(m+1, vector<int>(4200, -1));
rep(i, m) {
int num = 0;
rep(j, c[i].size()) {
num += pow(2, c[i][j]-1);
}
dp[i+1][num] = a[i];
for (int bit = 1; bit < (1<<n); bit++) {
if(dp[i][bit] > -1) {
if(dp[i+1][bit] == -1) {
dp[i+1][bit] = dp[i][bit];
} else {
chmin(dp[i+1][bit], dp[i][bit]);
}
int state = bit | num;
if(dp[i+1][state] == -1) {
dp[i+1][state] = dp[i][bit] + a[i];
} else {
chmin(dp[i+1][state], dp[i][bit] + a[i]);
}
}
}
}
cout << dp[m][(1<<n)-1] << endl;
return 0;
}