1.题目描述：点击打开链接
2.解题思路：本题利用集合上的动态规划解决。定义集合s1表示恰好有一个人教的课程，集合s2表示至少有两个人教的课程。定义d(i,s1,s2)表示已经考虑了前i个人时的最小花费（人物编号从0开始）。则不难写出状态转移方程：
d(i,s1,s2)=min{d(i+1,s1′,s2′)+c[i],d(i+1,s1,s2)};
上式中只有当i≥m时才会考虑第二项。对于这个方程的理解，重点在s1,s2集合的变化，随着s2集合不断扩大，花费的资金也应当越少，当s2恰好等于所有科目的集合时，不需要花钱，i只是对阶段的描述。其实这也不难理解，没有一个教师来教书的时候（即i=0时），肯定是学校要花钱最多的时候，当所有的教师都应聘完毕了，课程都有人教了，自然花费就少了。
本题的一个重要技巧就是利用位运算来解决各种集合之间的关系，另外一个小技巧就是设置一个辅助的参数s0，来方便集合之间的运算：将d(i,s1,s2)改为d(s0,s1,s2)，其中s0表示没有任何人能教的科目的集合。对于方程中s1′,s2’的计算，详见代码。注意：由于本题中的课程是从1开始编号的，而集合中是从0开始处理的，因此在输入时要预处理。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;const int maxn = 120+10;const int maxs = 8 + 1;#define INF 100000000int m, n, s;int c[maxn], st[maxn];//数组c表示工资，st表示第i个老师教课的集合int d[maxn][1 << maxs][1 << maxs];int dp(int i, int s0, int s1, int s2){if (i == m + n)return s2 == (1 << s) – 1 ? 0 : INF;//如果s2恰好等于全部课程的集合时，已经满足题意，，不需要花钱int&ans = d[i][s1][s2];if (ans >= 0)return ans;ans = INF;if (i >= m)ans = dp(i + 1, s0, s1, s2);//不选第i个应聘者，由于选i应聘者会导致s0,s1,s2改变，因此先初始化成不选int m0 = st[i] & s0;//只有第i个应聘者会教的课程int m1 = st[i] & s1;//第i个应聘者也会教的课程s0 ^= m0;//在s0集合中除去所有只有i应聘者会教的课程，即m0s1 = (s1^m1) | m0;//m1代表的所有课程变为了至少两个人会教，从s1中除去，同时加上m0s2 |= m1;//将m1添加到s2ans = min(ans, c[i] + dp(i + 1, s0, s1, s2));//选第i个应聘者，取较小者return ans;}int main(){//freopen("test.txt", "r", stdin);while (~scanf("%d%d%d", &s, &m, &n) && s&&m&&n){memset(d, -1, sizeof(d));memset(st, 0, sizeof(st));memset(c, 0, sizeof(c));getchar();for (int i = 0; i < m + n; i++){string str;getline(cin, str);stringstream ss(str);int x,flag=1;while (ss >> x){if (flag){ flag = 0; c[i] = x; }else{x–;st[i] |= (1<<x);}}}int ans = dp(0, (1 << s) – 1, 0, 0);printf("%d\n", ans);}return 0;}
正确的寒暄必须在短短一句话中明显地表露出你对他的关怀。
