UVA10817-Headmaster's Headache（动态规划基础）

Problem UVA10817-Headmaster's Headache

Time Limit: 4500 mSec

Problem Description

Input

The input consists of several test cases. The format of each of them is explained below: The ﬁrst line contains three positive integers S, M and N. S (≤ 8) is the number of subjects, M( ≤ 20) is the number of serving teachers, and N (≤ 100) is the number of applicants. Each of the following M lines describes a serving teacher. It ﬁrst gives the cost of employing him/her (10000 ≤ C ≤ 50000), followed by a list of subjects that he/she can teach. The subjects are numbered from 1 to S. You must keep on employing all of them. After that there are N lines, giving the details of the applicants in the same format. Input is terminated by a null case where S = 0. This case should not be processed.

Output

For each test case, give the minimum cost to employ the teachers under the constraints.

Sample Input

2 2 2

10000 1

20000 2

30000 1 2

40000 1 2

0 0 0

Sample Output

60000

题解：状压dp，但是比较麻烦的地方在于不少于2人，因此最直接的想法就是三进制枚举，不过三进制写起来有些麻烦，转念一想，其实可以用两个二进制位来代替这个三进制，我的两个二进制位的状态定义其实有些问题，比较正的思路就是前八位和后八位分别代表一个和大于等于两个。我的代码是跟着lrj的思路做的，实现的思路还是很好的，三进制可以转成两个二进制，用两个集合来表示整个状态，很值得学习（好写嘛），状态定义为dp[i][s1][s2]，表示考虑到前i个人，在状态（s1,s2）之下到达目标状态还要花费多少。这样方程就很好写了。在转移状态的时候需要位运算，这个硬想是很困难的，画个图就很简单了，交，并，对称差分别对应&，|，^。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxs = , maxm = , maxn = ;

 const int INF = 1e9;

 int s, m, n;

 int cost[maxn + maxm], teach[maxn + maxm];

 int dp[maxm + maxn][ << maxs][ << maxs];

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

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

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

     if (ans >= ) return ans;

     ans = INF;

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

     int t0 = s0 & teach[i];        //new subjects

     int t1 = s1 & teach[i];

     s0 ^= t0; s1 = (s1^t1) | t0; s2 |= t1;

     ans = min(ans, DP(i + , s0, s1, s2) + cost[i]);

     return ans;

 }

 int main()

 {

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

     string str;

     while (getline(cin, str)) {

         stringstream ss(str);

         ss >> s >> m >> n;

         if (s == ) break;

         memset(teach, , sizeof(teach));

         memset(dp, -, sizeof(dp));

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

             getline(cin, str);

             stringstream ss(str);

             ss >> cost[i];

             int t;

             while (ss >> t) {

                 t--;

                 teach[i] |= ( << t);

             }

         }

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

     }

     return ;

 }

巴特西