贴上我比较拙的代码，留念一下。
/**
* 想到状态压缩的dp问题就解决了一半。
*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <set>
using namespace std;
typedef long long int LL;
const int maxn=1e6+10;
vector<int> status[20];//存储每个项目对赢工程师的分配状态；
int project[15][5],engineer[15][5];//接收输入数据
bool have[105];//用来判断某些工程师的组合能否完成某一个项目
int dp[15][1029];//dp[i][s]前i个项目分配状态为s最对完成多少个项目；
//那么转移方程 dp[i][s]=max(dp[i-1][s-status]+1,dp[i-1][s]);
int n,m;
bool judge(int p,int status) //判断该选择工程师的状态能否完成第p个项目；
{
memset(have,0,sizeof(have));
for(int i=0;i<m;i++)
{
if(status&(1<<i))
{
for(int k=1;k<=engineer[i+1][0];k++)
have[engineer[i+1][k]]=1;
}
}
for(int i=1;i<=project[p][0];i++)
if(have[project[p][i]]==0) return false;
return true;
}
int main()
{
int ncase,cas=1;
scanf("%d",&ncase);
while(ncase--)
{
printf("Case #%d: ",cas++);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
status[i].clear();
scanf("%d",&project[i][0]);
for(int j=1;j<=project[i][0];j++) scanf("%d",&project[i][j]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&engineer[i][0]);
for(int j=1;j<=engineer[i][0];j++) scanf("%d",&engineer[i][j]);
}
for(int i=1;i<=n;i++)
for(int s=0;s<(1<<m);s++)
if(judge(i,s)) status[i].push_back(s);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int s=0;s<(1<<m);s++)
{
for(int j=0;j<(int)status[i].size();j++)
{
if((s|status[i][j])==s)
{
dp[i][s]=max(dp[i][s],dp[i-1][s-status[i][j]]+1);
}
}
dp[i][s]=max(dp[i][s],dp[i-1][s]);
//printf("dp[%d][%d]=%d
",i,s,dp[i][s]);
}
}
int cnt=(1<<m)-1;
printf("%d
",dp[n][cnt]);
}
return 0;
}
/*
1
10 10
3 25 10 10
3 20 20 20
3 25 10 10
3 20 20 20
3 25 10 10
3 20 20 20
3 25 10 10
3 20 20 20
3 25 10 10
3 20 20 20
2 20 10
2 20 10
2 20 10
2 20 10
2 20 10
2 20 10
2 20 10
2 20 10
2 20 10
2 20 10
*/