题目链接：

题意：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 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include
          
            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<
           
            =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<