题目地址：
?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1758
题目意思：
某校有n个教师和m个求职者。已知每人的工资和能教授的课程集合，要求支付最少的工资使得每门课都至少有两名教师教学。在职教师必须招聘
思路：m个求职者只有招和不招两种情况，0，1背包，只不过背包容量变抽象了而已，“每门课都至少有两名教师教学”是容量，如何表示从0容量转移到最终总容量需要细化状态，再定义一个"当前只有一个人教的课程集合"为另一维的状态就可以实现状态转移了
//765 ms C++ 4.8.2 1378 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int inf = 0x3f3f3f3f;int dp[125][1<<8][1<<8];int v[125];int st[125];int s,n,m;int main(){while(scanf("%d%d%d",&s,&n,&m)&&s){for(int i=0;i<n+m;i++){scanf("%d",&v[i]);int t=0;while(1){int tmp;if(getchar()=='\n') break;scanf("%d",&tmp);t|=(1<<(tmp-1));}st[i]=t;}memset(dp,0x3f,sizeof(dp));dp[0][0][0]=0;for(int i=0;i<m+n;i++)for(int s1=0;s1<(1<<s);s1++)for(int s2=0;s2<(1<<s);s2++){if(s1&s2) continue;if( i>=n )dp[i+1][s1][s2] =min(dp[i+1][s1][s2] , dp[i][s1][s2]);int t=( (1<<s)-1 )^(s1|s2);int S2=s2|(s1&st[i]);int S1=(s1|(st[i]&t))^(s1&st[i]);dp[i+1][S1][S2]=min(dp[i+1][S1][S2], dp[i][s1][s2]+v[i] );}int ans=inf;for(int s1=0; s1<(1<<s) ;s1++){if(s1&((1<<s)-1)) continue;ans=min(ans,dp[m+n][s1][(1<<s)-1]);}printf("%d\n",ans);}return 0;}由于枚举状态会产生很多不符合条件的状态，，所以用记忆化搜索可以大大加速：
//AcceptedC++0.569#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int inf = 0x3f3f3f3f;int dp[125][(1<<8)][(1<<8)];int n,m,s;int v[125];int st[125];int mrize(int i,int s0,int s1,int s2){if(i==m+n) return s2==(1<<s)-1 ? 0:inf;int &ans =dp[i][s1][s2];if( ans>=0 ) return ans;ans=inf;if(i>=n)ans=min(ans,mrize(i+1,s0,s1,s2));s2|=(s1&st[i]);s1 =(s1|(s0&st[i]))^(s1&st[i]);s0^=(s0&st[i]);ans=min(ans,mrize(i+1,s0,s1,s2)+v[i]);return ans;}int main(){while(scanf("%d%d%d",&s,&n,&m)&&s){memset(dp,-1,sizeof(dp));for(int i=0;i<n+m;i++){scanf("%d",&v[i]);int t=0;while(1){int tmp;if(getchar()=='\n') break;scanf("%d",&tmp);t|=(1<<(tmp-1));}st[i]=t;}printf("%d\n",mrize(0,(1<<s)-1,0,0));}return 0;}
不敢面对自己的不完美，总是担心自己的失败，
