比赛 东方幻想乡 S1 评测结果 RRRRRRRRRRRRRRRRRRRR
题目名称 东风谷早苗 最终得分 0
用户昵称 fflyt 运行时间 0.034 s
代码语言 C++ 内存使用 0.38 MiB
提交时间 2012-08-07 18:53:24
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;

int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	
	int n,v;cin>>n>>v;
	
	bool flag[40001]={0};
	int save[40001]={0};
	int c,w,num,non[20],nof,weight[20],cost[20],temp;
	int i,j,k;
	for(i=0;i<n;i++)
	{
		cin>>c>>w>>num;
		nof=1;
		non[1]=1;
		temp=0;
		for(j=1;;j++)
		{
			temp+=non[j];
			if(temp<num)
			{
				non[j+1]=2*non[j];
				nof++;
				continue;
			}
			if(temp==num) break;
			if(temp>num)
			{
				non[j]=num-temp+non[j];
				break;
			}
		}
		
		
		for(j=1;j<=nof;j++)
		{
			weight[j]=non[j]*w;
			cost[j]=non[j]*c;
			
			
		}
		
		
		save[v-weight[1]]=cost[1];
		flag[v-weight[1]]=1;
		for(j=1;j<=nof;j++)
		{
			
			for(k=v;k>=weight[j];k--)
			{
				if(flag[k-weight[j]]==1)
				{
					//save[k]=max(save[k],save[k-weight[j]]+cost[j]);
					if(save[k-weight[j]]+cost[j]>save[k])
					{
						save[k]=save[k-weight[j]]+cost[j];
						flag[k]=1;
					}
					
				}
			}
			
			
			for(k=1;k<=v;k++)cout<<save[k]<<' ';cout<<endl;
			
		}
		
		
		
	}
	
	int ans=0;
	for(i=v;i>=0;i--)
		if(save[i]>ans) ans=save[i];
	
	cout<<ans<<endl;
	
	
	return 0;
}