UVA 10817-Headmaster’s Headache（状态压缩DP）

题目大意：有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
  
   
#include
   
     #include
    
      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
     
      ='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
      
       ='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
       
        ='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
        
         ='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; }