题目大意：有S（S<=8）门课程，每门课程要求至少有2名老师教，雇佣每个老师需要一定的花费，每个老师可以教一门或多门课程。现有M（M<=20）名在职老师，N（N<=100）名应聘者，对于在职老师，必须每个都雇佣，求在满足每门课程至少2个老师教的情况下最少的花费是多少。
用d[i][j]表示前i名老师状态为j的情况下最少的花费，j是S位三进制数，对于每一位三进制位u，，为0时表示课程u当前没有老师教，为1表示课程u当前有一名老师教，为2表示课程u当前有两名老师教。最终答案为d[N][3^S-1]。
计算d[i][j]时，考虑是否雇佣第i位老师完成状态转移，如果雇佣，那么尽量充分利用这个老师所教的课程，对于这个老师教的每一门课，如果当前的j的那一门课对应三进制位大于0，那么减1，否则不变。
状态转移方程：d[i][j]=max { d[i-1][j],d[i-1][v]+cost[i] }（v为将可以减去的课程减去之后的状态）
#include<stdio.h>#include<stdlib.h>#include<string.h>char a[300];int b[105][10];int c[10];int d[105][7300];int co[105];int basethre[7100][10];int basetco[10];int main(void){int i,j,u,m,n,p,q,lo,sum,sump,minp,OK;q=1;for(i=1;i<=8;i++){basetco[i]=q;q=q*3;}for(i=0;i<q;i++){p=i;for(j=1;j<=8;j++){u=p%3;basethre[i][j]=u;p=p/3;if(p==0){break;}}}scanf("%d%d%d",&p,&n,&m);getchar();while((n!=0)||(p!=0)||(m!=0)){q=1;for(i=1;i<=p;i++){q=q*3;}q–;sum=0;for(i=1;i<=n;i++){gets(a);lo=strlen(a);for(j=0;j<lo;j++){if((a[j]>='0')&&(a[j]<='9')){sump=0;while((a[j]>='0')&&(a[j]<='9')){sump=sump*10+a[j]-'0';j++;}sum=sum+sump;break;}}for(u=j;u<lo;u++){if((a[u]>='0')&&(a[u]<='9')&&(c[a[u]-'0']<2)){c[a[u]-'0']++;}}}for(i=1;i<=m;i++){gets(a);lo=strlen(a);for(j=0;j<lo;j++){if((a[j]>='0')&&(a[j]<='9')){sump=0;while((a[j]>='0')&&(a[j]<='9')){sump=sump*10+a[j]-'0';j++;}co[i]=sump;break;}}for(u=j;u<lo;u++){if((a[u]>='0')&&(a[u]<='9')){b[i][a[u]-'0']=1;}}}d[0][0]=sum;for(j=1;j<=q;j++){OK=1;for(u=1;u<=p;u++){if(basethre[j][u]>c[u]){OK=0;break;}}if(OK==1){d[0][j]=sum;}else{d[0][j]=1000000000;}}for(i=1;i<=m;i++){d[i][0]=sum;for(j=1;j<=q;j++){minp=d[i-1][j];sump=0;for(u=1;u<=p;u++){if((basethre[j][u]>0)&&(b[i][u]==1)){sump=sump+basetco[u];}}if(minp>d[i-1][j-sump]+co[i]){minp=d[i-1][j-sump]+co[i];}d[i][j]=minp;}}printf("%d\n",d[m][q]);for(i=0;i<=10;i++){c[i]=0;}memset(b,0,sizeof(b));scanf("%d%d%d",&p,&n,&m);getchar();}return 0;}
才能做到人在旅途，感悟人生，享受人生。
