URAL/1326

来自"NOCOW"

啊~实在不想写了。。。

所以就直接暴力啦~

其实不用枚举这麽多状态的。。。

#include <iostream>
#include <cstring>
using namespace std;
int n,m,t1,t2,target=0,tot=0,ans=(~0U>>1);
int t[121][2]={0},f[1<<20];
int main()
{
    cin >> n;
    for (int i=0;i<n;++i)
    {
        cin >> t[++tot][0];
        t[tot][1]=(1<<i);
    }
    cin >> m;
    for (int i=1;i<=m;++i)
    {
        cin >> t[++tot][0] >> t1;
        for (int j=1;j<=t1;++j)
        {
            cin >> t2;
            t[tot][1]|=(1<<t2-1);
        }
    }
    cin >> t1;
    for (int i=1;i<=t1;++i)
    {
        cin >> t2;
        target|=(1<<t2-1);
    }
    memset(f,44,sizeof(f));
    f[0]=0;
    for (int i=1;i<=tot;++i)
        for (int j=0;j<(1<<n);++j)
            f[j|t[i][1]]=min(f[j|t[i][1]],f[j]+t[i][0]);
    for (int i=0;i<(1<<n);++i)
        if ((target&i) >= target)
            ans=min(ans,f[i]);
    cout << ans << endl;
    return 0;
}
//by zzy