题意：就是有个学校要招老师．要让没门课至少有两个老师可以上．每个样样例先输入三个数字课程数量ｓ，已经在任的老师数量，和应聘的老师数量．已经在任的一定要聘请．
思路是参考了刘汝佳书上的，关键如何状压。
#include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <algorithm> using namespace std; #define ll long long #define _cle(m, a) memset(m, a, sizeof(m)) #define repu(i, a, b) for(int i = a; i < b; i++) #define repd(i, a, b) for(int i = b; i >= a; i--) #define sfi(n) scanf("%d", &n) #define pfi(n) printf("%d ", n) #define sfi2(n, m) scanf("%d%d", &n, &m) #define pfi2(n, m) printf("%d %d ", n, m) #define pfi3(a, b, c) printf("%d %d %d ", a, b, c) #define MAXN 125 #define MAXS 8 const int INF = 0x3f3f3f3f; int c[MAXN], m, n, s, st[MAXN], d[MAXN][1<<MAXS][1<<MAXS]; int dp(int i, int s0, int s1, int s2) { if(i == m + n) return s2 == (1<<s) - 1 ? 0 : INF; int &ans = d[i][s1][s2]; if(ans >= 0) return ans; ans = INF; if(i >= m) ans = dp(i + 1, s0, s1, s2); int m0 = st[i] & s0, m1 = st[i] & s1; s0 ^= m0, s1 = (s1 ^ m1) | m0, s2 |= m1; ans = min(ans, c[i] + dp(i + 1, s0, s1, s2)); return ans; } int main() { while(1) { sfi2(s, m), sfi(n); if(s == 0) break; _cle(d, -1); _cle(st, 0); char ch; int ss; repu(i, 0, m + n) { sfi(c[i]); while(1) { sfi(ss); ch = getchar(); ss--; st[i] += (1<<ss); if(ch == ' ') break; } } pfi(dp(0, (1<<s) - 1, 0, 0)); //pfi(d[m + n - 1][0][(1<<s) - 1]); } return 0; }