记录编号	96664	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14] 奶牛的十项全能	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	1.825 s
提交时间	2014-04-14 14:31:15	内存使用	4.32 MiB

#include<fstream>
using namespace std;
ifstream fin("deca.in");
ofstream fout("deca.out");
int F[1<<20]={0},skill[21][21]={{0}};
int N,B;
struct award
{
	int k,p,a;
}w[21];
int NUM(int x)
{
	int sum=0;
	while(x)
	{
		sum+=x%2;
		x/=2;
	}
	return sum;
}
int main()
{
	fin>>N>>B;
	int i,j,k,l;
	for(i=1;i<=B;i++) fin>>w[i].k>>w[i].p>>w[i].a;
	for(i=1;i<=N;i++)for(j=1;j<=N;j++)fin>>skill[i][j];
	for(i=1,j=1;i<(1<<N);i<<=1,j++)
	{
		F[i]=skill[j][1];
		for(k=1;k<=B;k++) if(w[k].k==1&&w[k].p<=skill[j][1]) F[i]+=w[k].a;
	}
	for(i=1;i<(1<<N);i++)
	{
		int sum=NUM(i);
		for(j=1,k=1;j<i;j<<=1,k++)
		{
			if(i&j)
			{
				int score=F[i-j]+skill[k][sum],add=0;
				for(l=1;l<=B;l++) if(w[l].k==sum&&w[l].p<=score) add+=w[l].a;
			    F[i]=max(F[i],score+add);
			}
		}
	}
	fout<<F[(1<<N)-1]<<endl;
	return 0;
}