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

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct re{
	int p,b,c;
} a[22];
int n,m,maxn,tem;
int f[1<<21];
int w[22][22];
int count(int x){
	int ans=0;
    while(x){
    	ans++;
    	x-=x&(-x);
    }
    return ans;
}
int main(){
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	int i,j,k;
    cin>>n>>m;
    maxn=(1<<n)-1;
    for(i=1;i<=m;++i){
    	scanf("%d%d%d",&a[i].p,&a[i].b,&a[i].c);
    }
    for(i=1;i<=n;++i)
      for(j=1;j<=n;++j)
        scanf("%d",&w[i][j]);
    for(i=1;i<=maxn;++i){
    	k=count(i);
    	for(j=1;j<=n;++j)
    	if ((i>>(j-1))&1)
    	f[i]=max(f[i],f[i-(1<<(j-1))]+w[j][k]);
    	tem=0;
    	for(j=1;j<=m;++j){
    		if (a[j].p==k && f[i]>=a[j].b) 
			tem+=a[j].c;
    	}
    	f[i]+=tem;
    }
    cout<<f[maxn]<<endl;
}