UVA 10817 Headmaster's Headache（DP +状态压缩）

Headmaster's Headache

he headmaster of Spring Field School is considering employing some new teachers for certain subjects. There are a number of teachers applying for the posts. Each teacher is able to teach one or more subjects. The headmaster wants to select applicants so that each subject is taught by at least two teachers, and the overall cost is minimized.

Input

The input consists of several test cases. The format of each of them is explained below:

The first line contains three positive integers S, M and N. S (≤ 8) is the number of subjects, M (≤ 20) is the number of serving teachers, and N (≤ 100) is the number of applicants.

Each of the following M lines describes a serving teacher. It first gives the cost of employing him/her (10000 ≤ C≤ 50000), followed by a list of subjects that he/she can teach. The subjects are numbered from 1 to S. You must keep on employing all of them. After that there are N lines, giving the details of the applicants in the same format.

Input is terminated by a null case where S = 0. This case should not be processed.

Output

For each test case, give the minimum cost to employ the teachers under the constraints.

Sample Input

Sample Output

60000


题目大意：某校有n个教师和m个求职者。已知每人的工资和能交的课程集合，要求支付最少的工资使得每门课都至少有两名教师教学。在职教师必须招聘

输入格式：每组数据的第一行为3个整数s、m和n（1<=s<=8,1<=m<=20,1<=n<=100），即科目的个数、在职教师个数和申请者个数：以下m行每行用一些整数描述一位在职教师，其中第一个整数c（1000<=c<=50000）是工资，接下来的若干整数是他能教的科目列表（课程编号为1~s之间的整数）；接下来的n行描述申请者，格式同上。输入结束标志为s=0.
输出格式：对于每组数据，输出工资总额的最小值。

分析：
　　每一个老师可以教多门课程，而且在职教师必须招聘，那么在职教师能教的课就应该全部教，假设他们教的课程达到状态st。那么答案就是
　　　　　　　　　　所有在职教师的工资+（完成最终状态-st状态）的所有求职工的工资

　　科目个数最多为8，用16位2进制数来表示。2进制中从右往左数，前8为表示有1位老师教该门课程，后8为表示有2位老师教（该位-8）的课程，当s=8时，00000010 00000001表示1个老师教第一门课，2个老师教第2门课。这样 11111111 00000000 即为所要求的目标状态，代码中用T表示。

　　令dp[i][j]表示在前 j 个求职工中达到状态 i的最小花费。用st表示当前状态，则
　　　　　　dp[i][j] = min{dp[i][j], dp[i][j+1], dp[i+第j个人能够教的科目][j+1] +第j个人的工资}

　　定义函数int DP(int st,int i)表示第ｉ个人开始到ｎ个人结束，从状态 st 开始到目标状态的最小花费。这里用到记忆化搜索。

　　题目中没有给出每个老师会教的课程的数目，而是直接给课程的编号，所以要用gets输入，用sscanf提取其中的数字，这里我用动态二维数组保存每个求职者能教的课程。
　　　　sscanf(*s,"%d",&y)表示从字符串s中取出第一个数字，并且保存在y中
　　　　isdigit()判断字符c是否是数字，当字符c我0-9时返回非0值，否则返回0。
　　　for(j=0;j<strlen(t);j++){

　　　　　　sscanf(t+j,"%d",&y);
　　　　　　for(;isdigit(t[j]);j++);
　　　　　　j++;
　　}

　比如对于一字符串t[]=“1 2 3 4”，先取出数字1，之后j是数字跳过，再往后从t+2开始，取出数字2...

代码如下：

 1 # include<iostream>
 2 # include<cstdio>
 3 # include<cstring>
 4 # include<vector>
 5 # include<cctype>    //isdigit()函数包含在ctype.h头文件中
 6 # define INF 0x3f3f3f3f    
 7 # define N (1<<16)+5
 8 using namespace std;
 9 
10 int min(int a,int b){
11     return a<b ? a : b;
12 }
13 
14 int s,m,n,st,T;
15 bool vis[N][105];    //记忆化搜索的标记
16 int dp[N][105];
17 int v[105];        //n位求职者的工资
18 vector<int>lesson[105];    //lesson[i][]表示第i个求职者会教科目的集合
19 
20 int DP(int st,int i){
21 
22     if(vis[st][i])
23         return dp[st][i];
24     vis[st][i] = true;
25     
26     if(st==T)
27         return dp[st][i]=0;
28     if(i==n)
29         return INF;
30     int next=st;
31 
32     int len=lesson[i].size();    //第i个求职者会教科目的总数
33     for(int j=0;j<len;j++){
34         int y=lesson[i][j];
35         if(1<<(s+y) & next)    //如果已经有2位老师教该课程
36             continue;
37         if((1<<y) & next)    //如果已经有1位老师教该课程
38             next = next-(1<<y)+(1<<(s+y));
39         else    //如果没有老师教该课程
40             next = next + (1<<y);
41     }
42     if(next != st)
43         dp[st][i] = min(dp[st][i],DP(next,i+1)+v[i]);
44     dp[st][i] = min(dp[st][i],DP(st,i+1));
45     return dp[st][i];
46 }
47 
48 int main(){
49     int i,j,x,y;
50     char t[100];    //临时用来保存老师会教科目的集合，因为没有给出这个集合中元素的个数，所以要用gets输入
51     while(scanf("%d%d%d",&s,&m,&n) && s)
52     {
53         int ans = 0;    //保存结果
54         st = 0;    //表示在职教师能够教的课程的集合
55         memset(vis,0,sizeof(vis));    //初始化
56         memset(dp,INF,sizeof(dp));
57         for(i=0;i<m;i++)    //在职教师
58         {
59             scanf("%d",&x);
60             ans += x;    //因为在职教师必须招聘
61             gets(t);
62             int k =strlen(t);
63             for(j=0;j<k;j++){
64                 sscanf(t+j,"%d",&y);    //用sscanf提取工资后面的数组，y就是该教师所会的科目
65                 y--;    //只是将1~8门课程变成0~7门课程，便于2进制运算
66                 for(;isdigit(t[j]);j++);    //跳过是数字的字符    
67                 j++;    //那么往前走一步，下一次就能取到下一个数字了
68                 if(1<<(s+y)&st)
69                     continue;
70                 if(1<<y&st)
71                     st = st-(1<<y)+(1<<(s+y));
72                 else
73                     st = st+(1<<y);
74             }
75         }
76         for(i=0;i<n;i++) lesson[i].clear();
77         for(i=0;i<n;i++){
78             scanf("%d",&v[i]);
79             gets(t);
80             int k = strlen(t);
81             for(j=0;j<k;j++){
82                 sscanf(t+j,"%d",&y);
83                 lesson[i].push_back(y-1);
84                 for(;isdigit(t[j]);j++);    //跳过是数字的字符    
85                 j++;
86             }
87         }
88         T = 0;    //需要达成的状态
89         for(i=s;i<2*s;i++)
90             T += (1<<i);
91 
92         printf("%d
",ans+DP(st,0));
93     }
94     return 0;
95 }

好辛苦啊，为了看懂用了3个小时。。。不过还有疑问，为什么INF要在0x3f3f3f3f这个范围左右，改成其他的就不对了