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

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=20;
int N,B,k,p,b,x;
int f[1<<MAXN],skill[MAXN][MAXN];
vector<pii>bonus[MAXN];
int bitcount(int x){return x==0?0:bitcount(x>>1)+(x&1);}
int award(int score,int event)
{
	int size=bonus[event].size();
	for(int i=0;i<size;i++)
	{	
		if(score<bonus[event][i].first)break;
	    score+=bonus[event][i].second;
	}
	return score;
}
int main()
{
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	scanf("%d%d",&N,&B);
	int i,j;
	for(i=0;i<B;i++)
	{
		scanf("%d%d%d",&k,&p,&b);
		k--;
		bonus[k].push_back(pii(p,b));
	}
	for(i=0;i<N;i++)
		sort(bonus[i].begin(),bonus[i].end());
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			scanf("%d",&skill[i][j]);
	for(i=1;i<(1<<N);i++)//
	{   
		int b=bitcount(i);
		for(j=0;j<N;j++)//第j头牛完成第b-1个工作
		{
			if(i&(1<<j))
			{
				x=f[i^(1<<j)]+skill[j][b-1];
				if(f[i]<x)
					f[i]=x;
			}
		}
		f[i]=award(f[i],b-1);
	}   
	printf("%d\n",f[(1<<N)-1]);
	return 0;
}