比赛 |
东方幻想乡 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;
}