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

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,b;
struct node{
	int p,a;
};
node e[25][25];
int sum[25];
int f[25][1<<20],s[25][25];

void init(){
	int i,j,k;
	scanf("%d%d",&n,&b);
	for (i=1;i<=b;i++){
		scanf("%d",&k);
		sum[k]++;
		scanf("%d%d",&e[k][sum[k]].p,&e[k][sum[k]].a);
	}
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
		scanf("%d",&s[i][j]);
}

int calc(int x){
	int i,temp=0;
	for (i=1;i<1<<n;i<<=1)
	if (x & i) temp++;
	return temp;
}
	

void DP(){
	int i,j,k,t,temp,ans,cow,extra;
	for (i=1;i<=n;i++){
		for (j=1<<(i-1);j<1<<n;j++){
			if (calc(j)!=i) continue;
			cow=0;ans=0;
			for (k=1;k<1<<n;k<<=1){
				cow++;
				if (!(j & k)) continue;
				temp=f[i-1][j^k]+s[cow][i];
				extra=0;
				for (t=1;t<=sum[i];t++)
					if (temp>=e[i][t].p) extra+=e[i][t].a;
				temp+=extra;
				ans=max(ans,temp);
			}
			f[i][j]=ans;
		}
	}
	printf("%d\n",f[n][(1<<n)-1]);
}
			

int main(){
freopen("deca.in","r",stdin);
freopen("deca.out","w",stdout);
	init();
	DP();

	return 0;
}