90分蒟蒻求助

P1064 [NOIP2006 提高组] 金明的预算方案

主编稻草一号 @ 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


|