前置知识：

状压：

用二进制（或n进制）代表的十进制数来表示状态，通过位操作进行状态调整。
举个例子，房间内4盏灯的亮灭情况为0101，该状态存储下的十进制数为5。

从右往左编号为0，1，2，3。打开第3盏灯即将原状态5变为5|(1<<3)。
关于状压只做简单介绍。

枚举二进制子集：

二进制数为s，枚举其子集的含义是指，枚举所有x∈{x| x|s=s}。
具体操作如下：

for (int i = s; i; i = (i - 1) &ｓ)

这样就可以精确地枚举s的二进制子集，注意此时循环体中子集不包含0（空集），如要添加，需手动设置循环条件。

正文：

概述：

顾名思义，子集dp的状态转移，通常是由子集转移至当前集合，而有了枚举二进制子集的枚举方法之后，代码写起来会非常舒服，可以拥有更优秀的复杂度。

框架：

用转移方程dp[S]=dp[S⊕T]+max(dp[T])，T⊆S且T≠Ø为例，其中S⊕T含义是T关于S的补集，大体框架如下。

for(int i=0;i<1<<n;i++)
{
    
	for(int j=S&(S-1);j;S&(j-1))
	{
    
		dp[S]=max(dp[S],dp[S^j]+dp[j]);
	}
}

复杂度证明：

枚举所有集合的子集。
${\sum }_{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)2^i=3^n$
也就是o(3ⁿ)。

例题（牛客练习赛49B）：

问题简述：就是这样

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

int p[20];
int plan[1<<20];
int dp[1<<20];

int num[1<<20];
int gt(int x)
{
    
    if(x==0)return 0;
    if(num[x])return num[x];
    int ans=0;
    int t=x;
    while(t!=0)
    {
    
        ans++;
        t-=t&-t;
    }
    return num[x]=ans;
}

int main()
{
    
    int n,m;
    scanf("%d%d",&n,&m);
    int sum=0;
    for(int i=0;i<n;i++)scanf("%d",&p[i]),sum+=p[i];
    sort(p,p+n,greater<int>());
    for(int i=1;i<=m;i++)
    {
    
        int tn;
        scanf("%d",&tn);
        int x=0;
        for(int j=1;j<=tn;j++)
        {
    
            int w;
            scanf("%d",&w);
            x|=1<<w-1;
        }
        plan[x]=1;
    }
    dp[0]=0;
    for(int i=1;i<1<<n;i++)
    {
    
        for(int j=i&(i-1);1;j=i&(j-1))
        {
    
            int e=0;
            if(plan[i^j])e=p[gt(i)-1];
            else e=0;
            dp[i]=max(dp[i],dp[j]+e);
            if(j==0)break;
        }
    }
    printf("%d\n",sum-dp[(1<<n)-1]);
    return 0;
}