UVa 10817 (状压DP + 记忆化搜索) Headmaster's Headache

时间：2020-12-12 21:06:24

题意：

一共有s(s ≤ 8)门课程，有m个在职教师，n个求职教师。

每个教师有各自的工资要求，还有他能教授的课程，可以是一门或者多门。

要求在职教师不能辞退，问如何录用应聘者，才能使得每门课只少有两个老师教而且使得总工资最少。

分析：

因为s很小，所以可以用状态压缩。

dp(i, s1, s2)表示考虑了前i个人，有一个人教的课程的集合为s1，至少有两个人教的集合为s2。

在递归的过程中，还有个参数s0，表示还没有人教的科目的集合。

其中m0, m1, s0, s1, s2的计算用到位运算，还是个不错的练习。

 #include <cstdio>

 #include <string>

 #include <iostream>

 #include <cstring>

 #include <sstream>

 using namespace std;

 const int maxs = ;

 const int maxn = ;

 const int INF = ;

 int s, m, n, c[maxn], st[maxn], d[maxn][<<maxs][<<maxs];

 int dp(int i, int s0, int s1, int s2)

 {

     if(i == m+n) return s2 == (<<s)- ?  : INF;

     int& ans = d[i][s1][s2];

     if(ans >= ) return ans;

     ans = INF;

     if(i >= m) ans = dp(i+, s0, s1, s2);

     int m0 = st[i]&s0, m1 = st[i]&s1;   //m0是该教师能教且现在没人教的科目，m1是能教且现在只有一个人教的集合

     s0 ^= m0; s1 = (s1^m1)|m0; s2 |= m1;

     ans = min(ans, c[i] + dp(i+, s0, s1, s2));

     return ans;

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int x;

     string line;

     while(getline(cin, line))

     {

         stringstream ss(line);

         ss >> s >> m >> n;

         if(s == ) break;

         memset(st, , sizeof(st));

         for(int i = ; i < m+n; ++i)

         {

             getline(cin, line);

             stringstream ss(line);

             ss >> c[i];

             while(ss >> x) st[i] |= ( << (x-));

         }

         memset(d, -, sizeof(d));

         printf("%d\n", dp(, (<<s)-, , ));

     }

     return ;

 }

代码君

相关文章