主编稻草一号 @ 2021-10-19 20:14:43
麻了,实在不知道错在哪里了QAQ
#include<bits/stdc++.h>
using namespace std;
int f[61][32005],v[61][10],w[61][10],head[61],head2[61];//v:价格 w:重要度 head:记录元素数 head2:记录第i个物品在第几组
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++)
{
int vv,bb,ww;
scanf("%d%d%d",&vv,&ww,&bb);
if(bb==0)
{
head[0]++;
head2[i]=head[0];
v[head[0]][0]=vv;
w[head[0]][0]=ww;
}
else
{
head[bb]++;
head2[i]=head2[bb];
v[head2[bb]][head[bb]]=vv;
w[head2[bb]][head[bb]]=ww;
}
}//head[0]是用来分组的,其余是用来标每组元素个数的
for(register int i=1;i<=head[0];i++)
{
int v0=v[i][0],v1=v[i][1],v2=v[i][2],w0=w[i][0],w1=w[i][1],w2=w[i][2];//最多共有5种情况:不取,取主,取主副1,取主副2,全取
for(register int j=n;j>=v0;j--)
{
if(f[i-1][j-v0]+v0*w0>f[i][j]&&j-v0>=0)
f[i][j]=max(f[i-1][j-v0]+v0*w0,f[i-1][j]);
if(f[i-1][j-v0-v1]+v0*w0+v1*w1>f[i][j]&&j-v0-v1>=0)
f[i][j]=max(f[i-1][j-v0-v1]+v0*w0+v1*w1,f[i-1][j]);
if(f[i-1][j-v0-v2]+v0*w0+v2*w2>f[i][j]&&j-v0-v2>=0)
f[i][j]=max(f[i-1][j-v0-v2]+v0*w0+v2*w2,f[i-1][j]);
if(f[i-1][j-v0-v1-v2]+v0*w0+v1*w1+v2*w2>f[i][j]&&j-v0-v1-v2>=0)
f[i][j]=max(f[i-1][j-v0-v1-v2]+v0*w0+v1*w1+v2*w2,f[i-1][j]);
}
}
printf("%d",f[head[0]][n]);
return 0;
}
by 主编稻草一号 @ 2021-10-19 20:16:10
错的是第四个点,答案16700,我16500,搞半天也没发现怎么回事……
by _8762 @ 2021-10-28 17:45:16
@主编稻草一号 我找出来了
by AdGats @ 2021-11-21 10:36:31
@主编稻草一号 巧了
by AdGats @ 2021-11-21 10:42:06
你这个二维的应该还要max一下dp[i][j]吧(大雾
by AdGats @ 2021-11-21 10:49:05
哦不对,二维dp第二层循环应该到0,要不然有点部分没办法传递
by Seudama @ 2022-01-17 23:38:57
当j < v[i]时应该dp[i][j] = dp[i-1][j];
我也碰到了相同的错误hh