原题大意
有一个学校想要聘请老师，要求每个学科都有两个以上的老师授课，并且要使总费用最小。有S（最多8个）个学科，现任的M（最多20个）个老师（你必须继续聘请他们），N（最多100个）份申请。后来的M行每行有至少两个整数，表示现任的老师的工资，和他所教授的课程（可能不止一个）。再后来的N行每行有也有至少两个整数表示聘请这个老师所需的费用，以及他所教授的课程（可能不止一个）。
算法分析
这题属于集合类型的动态规划,因为最多只有8门课，所以考虑状态压缩，用d(i,s1,s2)来表示状态，s1是恰好有一个人教的课程集合，s2是至少有两个人教的集合,i表示第i个决策阶段。
状态转移方程为 d(i,s1,s2) = min{d(i+1,s1’,s2’) + c[i],d(i+1,s1,s2)}。把所有人一起编号0~m-1是在职教师，m~n+m-1是应聘者。
程序代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <memory.h>
#define mem(a,b) memset(a, b, sizeof(a))
using namespace std;
const int maxs = 8;
const int maxn = 150;
const int INF = (1 << 28);
int m, n, s, c[maxn], st[maxn], d[maxn][1<<maxs][1<<maxs];
//c记录工资, st[i]表示第i个人能教课的集合
//s0表示没有任何人能教的科目集合，s0，s1，s2知道其中之二就可以算出剩下的
int dp(int i, int s0, int s1, int s2){
if(i == m+n) return s2 == (1 << s) - 1? 0 : INF;
int &ans = d[i][s1][s2];
if(ans >= 0) return ans;
ans = INF;
if(i >= m) ans = dp(i+1, s0, s1, s2);//不选
int m0 = st[i] & s0, m1 = st[i] & s1;
s0 ^= m0;
s1 = (s1 ^ m1) | m0;
s2 |= m1;
ans = min(ans, dp(i+1, s0, s1, s2) + c[i]);//选
return ans;
}
int main(){
//freopen("input.txt", "r", stdin);
int x;
string line;
while(getline(cin,line)){
stringstream ss(line);
ss >> s >> m >> n;
if(s == 0) break;
mem(d, -1);mem(st, 0);
for(int i = 0; i < m+n; i++)
{
getline(cin, line);
stringstream ss(line);
ss >> c[i];
while(ss >> x) st[i] |= (1 << (x-1));
}
printf("%d\n", dp(0, (1<<s)-1, 0, 0));
}
return 0;
}