#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 400002
struct PP
{
	int c,acc,below;
} q[420];
bool cmp(PP a,PP b)
{
	return a.below<=b.below;
}
int f[maxn];
int max(int a,int b) {return a>b? a:b;}
void zop(int c,int w,int v)
{
	int i;
	for(i=v;i>=c;i--)
		f[i]=max(f[i],f[i-c]+w);
}
void cp(int c,int w,int v)
{
	int i;
	for(i=c;i<=v;i++)
		f[i]=max(f[i-c]+w,f[i]);
}
void mp(int c,int w,int acc,int v)
{
	int k;
	if(acc*w>=v)
		cp(c,w,v);
	else
	{
		k=1;
		while(k<acc)
		{
			zop(k*c,k*w,v);
			acc-=k;
			k=k*2;
		}
		zop(acc*c,acc*w,v);
	}
}
int main()
{
	int n,c,acc,i,v,ans,j;
	while(scanf("%d",&n)!=EOF)
	{
		memset(f,0,sizeof(f));
		ans=acc=c=v=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&q[i].c,&q[i].below,&q[i].acc);
			if(q[i].below>v) v=q[i].below;
			if(q[i].c>c) c=q[i].c;
			if(q[i].acc>acc) acc=q[i].acc;
		}
		if(v==0||c==0||acc==0) { printf("0\n"); continue; }
		sort(q+1,q+n+1,cmp);
		for(i=1;i<=n;i++)
			mp(q[i].c,q[i].c,q[i].acc,q[i].below);
		for(i=1;i<=v;i++)
		   if(f[i]>ans) { ans=f[i]; j=i;}
        printf("%d\n",ans);
	}
	return 0;
}

• Re:自我感觉良好 125秒 (6) peargobble 2011-04-19 19:15:43