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

#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
ifstream fi("deca.in");
ofstream fo("deca.out");
const int MAXN=21;
int N,B,skill[MAXN][MAXN];
int f[1<<20];
class GIFT
{
public:
	int p,a;
};
vector <GIFT> gift[21];
int get_cow_sum(int tmp)
{
	int t=tmp,ans=0;
	while(t)
	{
		if(t%2)ans++;
		t/=2;
	}
	return ans;
}
int main()
{
	fi>>N>>B;
	int p_i,k_i,a_i;
	for(int i=1;i<=B;i++)
	{
		fi>>k_i>>p_i>>a_i;
		gift[k_i].push_back((GIFT){p_i,a_i});
	}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			fi>>skill[i][j];
	f[0]=0;
	for(p_i=1,k_i=1;p_i< (1<<N);p_i<<=1,k_i++)//预处理整2^k次方
	{
		f[p_i]=skill[k_i][1];
		for(unsigned int temp=0;temp<gift[1].size();temp++)
		{
			if(skill[k_i][1]>=gift[1][temp].p)
				f[p_i]+=gift[1][temp].a;
		}
	}
	for(int i=1;i< (1<<N);i++)
	{
		int cow_sum=get_cow_sum(i);
		int j,k,score,add_score;
		for(j=1,k=1;j<i;j<<=1,k++)
		{
			if(i&j)
			{
				score=f[i-j]+skill[k][cow_sum];
				add_score=0;
				for(unsigned int temp=0;temp<gift[cow_sum].size();temp++)
				{
					if(score>=gift[cow_sum][temp].p)
						add_score+=gift[cow_sum][temp].a;
				}
				f[i]=max(f[i],score+add_score);
			}
		}
	}
	fo<<f[(1<<N)-1]<<endl;
	return 0;
}