Shabby_fish @ 2019-11-01 20:11:43
背包做的
#include<iostream>
#include<cstdio>
using namespace std;
int zv[64]={},fv[25][2]={},vf[25]={},zp[64]={},fp[25][2]={},nv[25][5]={},np[25][5]={},f[32004]={},n,m;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
// freopen("bug.txt","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(c)
{
fv[c][vf[c]]=a;
fp[c][vf[c]++]=b*a;
// cout<<c<<"-"<<fv[c][vf[c]-1]<<"-"<<fp[c][vf[c]-1]<<endl;
}
else
{
zv[i]=a;
zp[i]=b*a;
}
}
// for(int i=1;i<=m;i++)
// cout<<"v-"<<i<<" "<<zv[i]<<":"<<fv[i][0]<<","<<fv[i][1]<<endl<<"q-"<<i<<" "<<zp[i]<<":"<<fp[i][0]<<","<<fp[i][1]<<endl;
for(int i=1;i<=m;i++)
{
nv[i][1]=zv[i];
nv[i][2]=zv[i]+fv[i][0];
nv[i][3]=zv[i]+fv[i][1];
nv[i][4]=zv[i]+fv[i][1]+fv[i][0];
np[i][1]=zp[i];
np[i][2]=zp[i]+fp[i][0];
np[i][3]=zp[i]+fp[i][1];
np[i][4]=zp[i]+fp[i][1]+fp[i][0];
// cout<<"nv["<<i<<"]["<<1<<"]="<<nv[i][1]<<",nv["<<i<<"]["<<2<<"]="<<nv[i][2]<<",nv["<<i<<"]["<<3<<"]="<<nv[i][3]<<",nv["<<i<<"]["<<4<<"]="<<nv[i][4]<<";"<<endl<<"np["<<i<<"]["<<1<<"]="<<np[i][1]<<",np["<<i<<"]["<<2<<"]="<<np[i][2]<<",np["<<i<<"]["<<3<<"]="<<np[i][3]<<",np["<<i<<"]["<<4<<"]="<<np[i][4]<<"."<<endl;
}
for(int i=1;i<=m;i++)
for(int j=n;j>=0;j--)
{
if(j>=nv[i][1]) f[j]=max(f[j],f[j-nv[i][1]]+np[i][1]);
if(j>=nv[i][2]) f[j]=max(f[j],f[j-nv[i][2]]+np[i][2]);
if(j>=nv[i][3]) f[j]=max(f[j],f[j-nv[i][3]]+np[i][3]);
if(j>=nv[i][4]) f[j]=max(f[j],f[j-nv[i][4]]+np[i][4]);
// cout<<"f["<<j<<"]"<<f[j]<<endl;
}
cout<<f[n];
return 0;
}
by Shabby_fish @ 2019-11-04 20:59:14
A 了
分享一下原因:数组开小了……
by 㸚茻㠭㗊 @ 2019-11-08 16:11:36
@叕㵘燚㙓 ??
by Shabby_fish @ 2019-11-08 16:28:54
@㸚茻㠭㗊 你不会做还瞎BB
by TonyWu @ 2020-02-18 21:00:54
码辣眼