UVa 10817 - Headmaster's Headache（状压DP）

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1758

题意：

某校有m个教师和n个求职者，需讲授s个课程（1≤s≤8，1≤m≤20，1≤n≤100）。
已知每人的工资c（10000≤c≤50000）和能教的课程集合，要求支付最少的工资使得每门课都至少有两名教师能教。在职教师不能辞退。

分析：

用两个集合：s1表示恰好有一个人教的科目集合，s2表示至少有两个人教的科目集合，
而d(i,s1,s2)表示已经考虑了第i个人及其之后所有人时的最小花费。
注意，把所有人一起从0编号，则编号0～m-1是在职教师，m～n+m-1是应聘者。
状态转移方程为d(i,s1,s2) = min{d(i+1, s1', s2')+c[i], d(i+1, s1, s2)}，其中第一项表示“聘用”，第二项表示“不聘用”。
当i≥m时状态转移方程才出现第二项。这里s1'和s2'分别表示“招聘第i个人之后s1和s2的新值”，具体计算方法见代码。
下面代码中的can[i]表示第i个人能教的科目集合（注意输入中科目从1开始编号，而代码的其他部分中科目从0开始编号，
因此输入时要转换一下）。下面的代码用到了一个技巧：记忆化搜索中有一个参数s0，表示目前还没有人教的科目集合。
这个参数并不需要记忆（因为有了s1和s2就能算出s0），仅是为了编程的方便（详见s1'和s2'的计算方式）。
最终结果是 dp(0, (1<s)-1, 0, 0)，因为初始时所有科目都没有人教。

代码：

 #include <cstdio>

 #include <cstring>

 #include <sstream>

 using namespace std;

 const int UP =  +  + ;

 const int INF = ;

 int s, m, n, c[UP], can[UP], d[UP][<<][<<];

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

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

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

     if(res >= ) return res;

     res = INF;

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

     int m0 = can[i] & s0, m1 = can[i] & s1;

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

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

     return res;

 }

 int main(){

     int temp;

     char str[];

     while(~scanf("%d%d%d\n", &s, &m, &n) && s){

         memset(can, , sizeof(can));

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

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

             gets(str);

             stringstream ss(str);

             ss >> c[i];

             while(ss){

                 ss >> temp;

                 can[i] |= ( << temp - );

             }

         }

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

     }

     return ;

 }

巴特西

UVa 10817 - Headmaster's Headache（状压DP）

最新文章

热门文章