首页 > 代码库 > UVa 10817 校长的烦恼
UVa 10817 校长的烦恼
https://vjudge.net/problem/UVA-10817
题意：
某校有m个教师和n个求职者，需讲授s个课程，已知每人的工资c和能教的课程集合，要求支付最少的工资使得每门课都至少有两名老师能教。
思路：
s1表示恰好有一个人教的科目集合，s2表示至少有两个人教的科目集合。
d[i][s1][s2]表示已经考虑了前i个人时的最小花费。参考了大神的代码，如下：
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<sstream> 5 #include<algorithm> 6 using namespace std; 7 8 9 const int maxn = 120 + 10;10 const int maxs = 8 + 1;11 #define INF 10000000012 int m, n, s;13 int c[maxn], st[maxn];//数组c表示工资，st表示第i个老师教课的集合14 int d[maxn][1 << maxs][1 << maxs];15 16 int dp(int i, int s0, int s1, int s2)17 {18 if (i == m + n)19 return s2 == (1 << s) - 1 ? 0 : INF;//如果s2恰好等于全部课程的集合时，已经满足题意，不需要花钱20 int& ans = d[i][s1][s2];21 if (ans >= 0)return ans;22 ans = INF;23 if (i >= m) ans = dp(i + 1, s0, s1, s2);//不选第i个应聘者，由于选i应聘者会导致s0,s1,s2改变，因此先初始化成不选24 int m0 = st[i] & s0;//只有第i个应聘者会教的课程25 int m1 = st[i] & s1;//第i个应聘者也会教的课程26 s0 ^= m0;//在s0集合中除去所有只有i应聘者会教的课程，即m027 s1 = (s1^m1) | m0;//m1代表的所有课程变为了至少两个人会教，从s1中除去，同时加上m028 s2 |= m1;//将m1添加到s229 ans = min(ans, c[i] + dp(i + 1, s0, s1, s2));//选第i个应聘者，取较小者30 return ans;31 }32 33 int main()34 {35 //freopen("D:\\txt.txt", "r", stdin);36 while (~scanf("%d%d%d", &s, &m, &n) && s&&m&&n)37 {38 memset(d, -1, sizeof(d));39 memset(st, 0, sizeof(st));40 getchar();41 for (int i = 0; i < m + n; i++)42 {43 string str;44 getline(cin, str);45 stringstream ss(str);46 int x, flag = 1;47 while (ss >> x)48 {49 if (flag){ flag = 0; c[i] = x; }50 else51 {52 x--; //将科目从0开始编号53 st[i] |= (1 << x); //二进制的压缩存储54 }55 }56 }57 int ans = dp(0, (1 << s) - 1, 0, 0);58 printf("%d\n", ans);59 }60 return 0;61 }
UVa 10817 校长的烦恼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。