1 /*
2 题意：学校有在任的老师和应聘的老师，选择一些应聘老师，使得每门科目至少两个老师教，问最少花费多少
3 状压DP：一看到数据那么小，肯定是状压了。这个状态不好想，dp[s1][s2]表示s1二进制表示下至少有1位老师的科目集合
4 s2表示至少有2位老师的科目集合所花费的最小金额，状态转移方程(01)：dp[t1][t2]=min(dp[t1][t2],dp[j][k]+c[i]);
5 j,k为当前两个集合，t1，t2为转移后的集合，另外求t1，t2用到了& |位运算 1&1 == 1 1 & 0 == 0 0 & 0 == 0
6 最后，学习了不知道数字多少个时应该用字符串整行读入
7 详细解释
8
9 */
10 /************************************************
11 * Author :Running_Time
12 * Created Time :2015-8-10 14:44:30
13 * File Name :UVA_10817.cpp
14 ************************************************/
15
16 #include <cstdio>
17 #include <algorithm>
18 #include <iostream>
19 #include <sstream>
20 #include <cstring>
21 #include <cmath>
22 #include <string>
23 #include <vector>
24 #include <queue>
25 #include <deque>
26 #include <stack>
27 #include <list>
28 #include <map>
29 #include <set>
30 #include <bitset>
31 #include <cstdlib>
32 #include <ctime>
33 using namespace std;
34
35 #define lson l, mid, rt << 1
36 #define rson mid + 1, r, rt << 1 | 1
37 typedef long long ll;
38 const int MAXN = 150;
39 const int INF = 0x3f3f3f3f;
40 const int MOD = 1e9 + 7;
41 int c[MAXN], p[MAXN], cnt[10];
42 int dp[(1<<8)+10][(1<<8)+10];
43 int s, m, n;
44 int mxs;
45 int sum, st1, st2;
46
47 int work(void) {
48 memset (dp, INF, sizeof (dp));
49 dp[st1][st2] = sum;
50 for (int i=m+1; i<=m+n; ++i) {
51 for (int j=mxs; j>=0; --j) {
52 for (int k=mxs; k>=0; --k) {
53 if (dp[j][k] == INF) continue;
54 int t1 = (p[i] | j); int t2 = (p[i] & j) | k;
55 dp[t1][t2] = min (dp[t1][t2], dp[j][k] + c[i]);
56 }
57 }
58 }
59 return dp[mxs][mxs];
60 }
61
62 int main(void) { //UVA 10817 Headmaster's Headache
63 while (scanf ("%d%d%d", &s, &m, &n) == 3) {
64 if (!s) break;
65
66 memset (cnt, 0, sizeof (cnt));
67 memset (p, 0, sizeof (p));
68 sum = 0, st1 = st2 = 0; mxs = (1 << s) - 1;
69 string str;
70 for (int i=1; i<=m+n; ++i) {
71 scanf ("%d", &c[i]);
72 getline (cin, str);
73 for (int j=0; str[j]; ++j) {
74 if (isdigit (str[j])) {
75 int x = str[j] - '0';
76 p[i] |= 1 << (x - 1);
77 if (i <= m) ++cnt[x-1];
78 }
79 }
80 if (i <= m) {
81 sum += c[i]; st1 |= p[i];
82 }
83 }
84 for (int i=0; i<s; ++i) {
85 if (cnt[i] > 1) st2 |= (1 << i);
86 }
87
88 printf ("%d
", work ());
89 }
90
91 return 0;
92 }
状压DP UVA 10817 Headmaster's Headache
编译人生，运行世界！