记录编号	254850	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2016-04-26 06:22:59	内存使用	1.46 MiB

#include<cstdio>
int v[65],w[65],p[65];
int group[65][65];
int gcnt=0;
int belong[65];
int _v[65][2049],_w[65][2049];
int log[2049];
int f[32005];
int lim[65];
int max(int a,int b){
	return a>b?a:b;
}
int main(){
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	int money,n,s;
	scanf("%d %d %d",&money,&n,&s);
	for(int i=1;i<=n;++i){
		scanf("%d %d %d",w+i,v+i,p+i);
		v[i]*=w[i];
		if(!p[i]){
			belong[i]=gcnt;
			group[gcnt][1]=i;
			group[gcnt][0]=2;
			gcnt++;
		}
	}
	for(int i=1;i<=n;++i){
		if(p[i]){
			belong[i]=belong[p[i]];
			group[belong[i]][group[belong[i]][0]++]=i;
		}
	}
	int tmp=1;
	for(int i=2;i<=10;++i){
        log[tmp]=i;tmp<<=1;
	}
	for(int i=0;i<gcnt;++i){
		//子集枚举
		lim[i]=1<<(group[i][0]-2);
		_v[i][0]=v[group[i][1]];
		_w[i][0]=w[group[i][1]];
		for(int j=1;j<lim[i];++j){
            int pre=j-(j&(-j));
            _v[i][j]=_v[i][pre]+v[group[i][log[j&(-j)]]];
            _w[i][j]=_w[i][pre]+w[group[i][log[j&(-j)]]];//1->2 2->3 4->4 8->5
		}
	}
	//分组背包
/*	for(int i=0;i<gcnt;++i){
        for(int k=0;k<lim[i];++k){
            printf("%d %d %d %d\n",i,k,_v[i][k],_w[i][k]);
        }
	}*/
	for(int i=0;i<gcnt;++i){
		for(int j=money;j>0;--j){
			for(int k=0;k<lim[i];++k){
				if(j>=_w[i][k])f[j]=max(f[j],f[j-_w[i][k]]+_v[i][k]);
			}
		}
	}
	printf("%d\n",f[money]);
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
2000 10 2
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5
7430
*/