UVA 10817

題目大意：有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;
}