题目地址:Headmaster’s Headache
刘汝佳的算法如下
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int INF=0x3f3f3f3f;
const int maxn=100+20+5;
const int maxs=8;
int m,n,s,c[maxn],st[maxn],d[maxn][1<<maxs][1<<maxs];
int DP(int i,int s0,int s1,int s2){ //选第i个人，还有哪些课没人教，只有一人教，至少两个人教if(i==m+n) return s2==(1<<s)-1?0:INF; //选好了int& ans=d[i][s1][s2];if(ans!=-1) return ans;ans=INF;if(i>=m) ans=DP(i+1,s0,s1,s2); //不选 (求职者)int m0=st[i]&s0, m1=st[i]&s1; //m0:第i个人可以教的 s0 的课程，m1:第i个人可以教的s1的课程s0^=m0; //更新s0, (交给i教，所以去掉m0部分)s1=(s1^m1)|m0; //更新s1 ,去叫m1部分，加上m0部分s2|=m1; //加上m1部分ans=min(ans,c[i]+DP(i+1,s0,s1,s2)); //选return ans;
}
int main(int argc, char const *argv[])
{while(scanf("%d%d%d ",&s,&m,&n)==3&&s+m+n){string line; int x;REP(i,0,n+m-1) {getline(cin,line);stringstream ss(line);ss>>c[i];st[i]=0;while(ss>>x) st[i]|=(1<<(x-1));}memset(d,-1,sizeof(d));printf("%d\n", DP(0,(1<<s)-1,0,0));}return 0;
}