CHNREST - Chinese restaurant
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
using namespace std;
int pow[11];
bool b[33][11];
int m, n;
int p[33];
int F[33][60000];
int go(int pos, int state) {
if(pos == m) {
if(state == pow[n] - 1) return 0;
else return 1000000000;
}
if(F[pos][state] != -1) return F[pos][state];
int res = go(pos + 1, state);
bool ok = true;
for(int i=0;i<n;++i)
if(b[pos][i] && state / pow[i] % 3 == 2) {
ok = false;
break;
}
if(ok) {
int ns = state;
for(int i=0;i<n;++i)
if(b[pos][i])
ns += pow[i];
res = min( res, p[pos] + go( pos + 1, ns));
}
return F[pos][state] = res;
}
int main() {
cin >> m >> n;
for(int i=0;i<m;++i) cin >> p[i];
string s;
getline( cin, s);
for(int i=0;i<n;++i) {
getline( cin, s);
istringstream iss(s);
int x;
while(iss >> x) {
b[x-1][i] = true;
}
}
pow[0] = 1;
for(int i=1;i<11;++i)
pow[i] = 3 * pow[i - 1];
memset( F, -1, sizeof(F));
int best = go( 0, 0);
if(best < 1000000000)
cout << best << endl;
else
cout << -1 << endl;
return 0;
}