首页 > 代码库 > UVa 10817 (状压DP + 记忆化搜索) Headmaster's Headache
UVa 10817 (状压DP + 记忆化搜索) Headmaster's Headache
题意：
一共有s(s ≤ 8)门课程，有m个在职教师，n个求职教师。
每个教师有各自的工资要求，还有他能教授的课程，可以是一门或者多门。
要求在职教师不能辞退，问如何录用应聘者，才能使得每门课只少有两个老师教而且使得总工资最少。
分析：
因为s很小，所以可以用状态压缩。
dp(i, s1, s2)表示考虑了前i个人，有一个人教的课程的集合为s1，至少有两个人教的集合为s2。
在递归的过程中，还有个参数s0，表示还没有人教的科目的集合。
其中m0, m1, s0, s1, s2的计算用到位运算，还是个不错的练习。
1 #include <cstdio> 2 #include <string> 3 #include <iostream> 4 #include <cstring> 5 #include <sstream> 6 using namespace std; 7 8 const int maxs = 8; 9 const int maxn = 125;10 const int INF = 1000000000;11 int s, m, n, c[maxn], st[maxn], d[maxn][1<<maxs][1<<maxs];12 13 int dp(int i, int s0, int s1, int s2)14 {15 if(i == m+n) return s2 == (1<<s)-1 ? 0 : INF;16 int& ans = d[i][s1][s2];17 if(ans >= 0) return ans;18 ans = INF;19 if(i >= m) ans = dp(i+1, s0, s1, s2);20 int m0 = st[i]&s0, m1 = st[i]&s1; //m0是该教师能教且现在没人教的科目，m1是能教且现在只有一个人教的集合21 s0 ^= m0; s1 = (s1^m1)|m0; s2 |= m1;22 ans = min(ans, c[i] + dp(i+1, s0, s1, s2));23 return ans;24 }25 26 int main()27 {28 //freopen("in.txt", "r", stdin);29 int x;30 string line;31 while(getline(cin, line))32 {33 stringstream ss(line);34 ss >> s >> m >> n;35 if(s == 0) break;36 37 memset(st, 0, sizeof(st));38 for(int i = 0; i < m+n; ++i)39 {40 getline(cin, line);41 stringstream ss(line);42 ss >> c[i];43 while(ss >> x) st[i] |= (1 << (x-1));44 }45 memset(d, -1, sizeof(d));46 printf("%d\n", dp(0, (1<<s)-1, 0, 0));47 }48 49 return 0;50 }
UVa 10817 (状压DP + 记忆化搜索) Headmaster's Headache
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。