记录编号	47114	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2012-10-30 20:51:17	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
struct shopping{
    int v,p;//v价格p重要度
    int flag;
    bool own;
    int con[2];//两个附件
}thing[61];
struct situation{
    int v,p,inc;//v价格p重要度
}s[250];
int fold[250]={0};
int main(){
    freopen("budget.in","r",stdin);
    freopen("budget.out","w",stdout);
    int n,m,i,j,v,p,q,sum=0,sumf=0,ans=-1;//n钱数m物数
    int f[32768]={0};
    for(i=0;i<61;i++) thing[i].flag=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&v,&p,&q);
        thing[i].v=v;
        thing[i].p=p;
        if(q>0){
            thing[i].own=false;
            if(thing[q-1].flag==0) thing[q-1].flag=1,thing[q-1].con[0]=i;
            else thing[q-1].flag=2,thing[q-1].con[1]=i;
        }
		else thing[i].own=true;
    }
    for(i=0;i<m;i++){
        if(thing[i].own==true){//非附件
			fold[sumf]=sum;
			sumf++;
            s[sum].v=thing[i].v;
            s[sum].p=thing[i].v*thing[i].p;
			s[sum].inc=(int)pow(2,(double)thing[i].flag);
            sum++;
            if(thing[i].flag>=1){//有附件
                s[sum].v=thing[i].v+thing[thing[i].con[0]].v;
                s[sum].p=thing[i].v*thing[i].p+thing[thing[i].con[0]].v*thing[thing[i].con[0]].p;
                sum++;
            }
            if(thing[i].flag>=2){//有2个附件
				s[sum].v=thing[i].v+thing[thing[i].con[1]].v;
                s[sum].p=thing[i].v*thing[i].p+thing[thing[i].con[1]].v*thing[thing[i].con[1]].p;
				sum++;
                s[sum].v=thing[i].v+thing[thing[i].con[0]].v+thing[thing[i].con[1]].v;
                s[sum].p=thing[i].v*thing[i].p+thing[thing[i].con[0]].v*thing[thing[i].con[0]].p+thing[thing[i].con[1]].v*thing[thing[i].con[1]].p;
                sum++;
            }
        }
    }
	int x,y,k;
	for(i=0;i<sumf;i++){
		x=fold[i];
		y=s[x].inc;
		for(j=n;j>=s[x].v;j--){
			for(k=x;k<=x+y-1;k++) if(j>=s[k].v&&f[j-s[k].v]+s[k].p>f[j]) f[j]=f[j-s[k].v]+s[k].p;
			if(f[j]>ans) ans=f[j];
		}
	}
    printf("%d",ans);
    return 0;
}