本文共 1480 字，大约阅读时间需要 4 分钟。
本文出自
某校有n个教师和m个求职者，已知每人的工资和能教的课程集合，要求支付最少的工资使得每门课都至少有两名教师教学。在职教师必须招聘。
这题不太好想,搞了很久。。
f[s1][s2]： s1表示课程集合{ s1 }都至少有一个教师教的情况。
s2表示课程集合{ s2 }都至少有两个教师教的情况。
每个求职者的pi, 对于每个求职者，要么选，要么不选，就是01背包问题。
对于s1，s2，可以根据当前枚举到的求职者课程即可，可推出下一个状态：
nextS1 = p[i] | s1,
nextS2 = (p[i] & s1) | s2
f[nextS1][nextS2] = min(f[nextS1][nextS2], f[s1][s2] + p[i])
/**========================================== * This is a solution for ACM/ICPC problem * * @problem: UVA 10817 - Headmaster's Headache * @type: dp * @author: shuangde * @blog: blog.csdn.net/shuangde800 * @email: zengshuangde@gmail.com *===========================================*/#include #include #include #include #include #include #include using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const double PI = acos(-1.0); const int MAXN = 150; int courseNum, m, n, sum; int maxState; int f[1<<8][1<<8]; int p[MAXN], c[MAXN], cnt[10]; int dp(int st1, int st2){ memset(f, 0x3f, sizeof(f)); f[st1][st2] = sum; for(int i=m+1; i<=n+m; ++i){ for(int s1=maxState; s1>=0; --s1){ for(int s2=maxState; s2>=0; --s2){ if(f[s1][s2] >= INF) continue; int st1 = (p[i]|s1); int st2 = (p[i]&s1) | s2; f[st1][st2] = min(f[st1][st2], f[s1][s2]+c[i]); } } } return f[maxState][maxState]; } int main(){ char str[1000]; while(~scanf("%d%d%d", &courseNum, &m, &n) && courseNum){ maxState = (1< 1) st2 |= (1<