Uva 10817 校长的烦恼

题目链接：https://uva.onlinejudge.org/external/108/10817.pdf

题意：m个教师，n个应聘者，s个课程，每个人的工资为c，每个人能教一些课程。求最少的支付费用，

使得，每个课程都有>=2名教师可以上，在职教师不能下岗。

分析：

dp(i,s1,s2)

已经考虑前 i 个人时，此时，课程只有一个人上的集合s1,两个或者以上的课程集合s2的最少费用;

关于课程集合：

首先一个老师的课程m0 = st&s0，就是他能上的没人上的课程集合，st&s1，就是他能上的一个人上的课程的集合，

选了他的话：

s2就是 s2 | m0；

s0就是 s0^m0;

s1 就是 (s1 ^ m1)减少的部分，加上 | m0.

还有，这里的输入很麻烦，没有确定每个人有多少课程。

首先用getline()输入一行，然后stringstream ss(line)，用ss>>x不停的输入;

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <string>
 5 #include <iostream>
 6 #include<sstream>
 7 
 8 using namespace std;
 9 const int INF = 1000000000;
10 const int maxn = 125;
11 
12 int m,n,s;
13 int c[maxn];
14 int st[maxn];
15 int d[maxn][1<<8][1<<8];
16 
17 
18 
19 int dp(int i,int s0,int s1,int s2)
20 {
21     if(i==m+n) return s2 == (1<<s)-1?0:INF;
22 
23     int& ans = d[i][s1][s2];
24     if(ans>=0) return ans;
25 
26     ans = INF;
27     if(i>=m) ans = dp(i+1,s0,s1,s2);
28 
29     int m0 = s0&st[i];
30     int m1 = s1&st[i];
31 
32     s0  = s0^m0;
33     s1 = (s1 ^ m1) | m0;
34     s2 = s2 | m1;
35 
36     ans = min(ans,c[i]+dp(i+1,s0,s1,s2));
37     return ans;
38 
39 }
40 
41 int main()
42 {
43     int x;
44     string line;
45     while(getline(cin, line))
46     {
47         stringstream ss(line);
48         ss >> s >> m >> n;
49         if(s == 0) break;
50 
51         for(int i = 0; i < m+n; i++)
52         {
53             getline(cin, line);
54             stringstream ss(line);
55             ss >> c[i];
56             st[i] = 0;
57             while(ss >> x) st[i] |= (1 << (x-1));
58         }
59         memset(d, -1, sizeof(d));
60         cout << dp(0, (1<<s)-1, 0, 0) << "
";
61     }
62     return 0;
63 }