有4个测试点没过，请问代码错在哪里？

tqychy @ 2022-01-25 23:19:11

#include<stdio.h>
int max(int a,int b);
int main()
{int i=0,j=0,n=0,m=0,tv=0,tq=0,tp=0,cntm=0,cnts=0;
scanf("%d %d",&m,&n);//m和n和题目是反的。 
int mainw[1+n];
int mainv[1+n];
int cntsides[1+n];
int sidew[1+n][2];//第二维0表示第一个附件，1表示第二个附件。
int sidev[1+n][2];
int dp[1+m];
for(i=0;i<=n;i++)
{
    mainw[i]=0;//主件的代价。 
    mainv[i]=0;//主件的价值。 
    cntsides[i]=0;//主件的附件数量。 
    for(j=0;j<=1;j++)
    {
        sidew[i][j]=0;//附件的代价。
        sidev[i][j]=0;//附件的价值。
    }
}
for(i=0;i<n;i++)
{
    scanf("%d %d %d",&tv,&tp,&tq);
    if(tq==0)
    {
        cntm++;
        mainw[cntm]=tv;
        mainv[cntm]=tp*tv;
    }
    else
    {
        sidew[tq][cntsides[tq]]=tv;
        sidev[tq][cntsides[tq]]=tp*tv;
        cntsides[tq]++;
    }
}
for(i=0;i<=m;i++){dp[i]=0;}
i=1;
while(mainv[i]!=0)
{
    for(j=m;j>0;j--)
    {
        if(j>=mainw[i]){dp[j]=max(mainv[i]+dp[j-mainw[i]],dp[j]);}
        if(cntsides[i]>0&&j>=sidew[i][0]+mainw[i])
        {
            dp[j]=max(sidev[i][0]+mainv[i]+dp[j-mainw[i]-sidew[i][0]],dp[j]);
        }
        if(cntsides[i]>1&&j>=sidew[i][1]+mainw[i])
        {
            dp[j]=max(dp[j],sidev[i][1]+mainv[i]+dp[j-mainw[i]-sidew[i][1]]);
        }
        if(cntsides[i]>1&&j>=sidew[i][0]+sidew[i][1]+mainw[i])
        {
            dp[j]=max(sidev[i][0]+sidev[i][1]+mainv[i]+dp[j-mainw[i]-sidew[i][1]-sidew[i][0]],dp[j]);
        }
    }
    i++;
}
printf("%d",dp[m]);
return 0;
}
int max(int a,int b)
{
    if(b>a){return b;}
    return a;
}

by Butterfly__qwq @ 2022-04-11 21:43:55

奇怪的码风，我刚AC看了你的WA代码又迷惑了

by JCLinux @ 2022-04-12 07:58:56

咱俩应该是一样的错，我把第一个WA的点下载下来跑了一下，我的结果是7200，你的也是，而正解是7430，我看了好半天没看明白为啥能拿到7430 后来突然想明白了，是题理解错了。 我大概人瞅了一眼的的输入部分的代码，和我一样统计了有几个主要物品。但是这个题目最坑的是:并不是第几个出现的主要物品编号是几，而是第几行出现的主要物品编号是几！

也就是说，主要物品并不是按照顺序给出的，中间可能有空。

by zo__Oz @ 2022-06-06 22:54:34

@JCLinux 我的也是这个问题，WA 3 7 8 9 看了您的才改过来 错误代码

#include<bits/stdc++.h>
using namespace std;
int n,m,N;
int V[150][3],P[150][3];
int dp[32005];

int main()
{
    scanf("%d%d",&n,&m);

    int v,p,q;
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d%d%d",&v,&p,&q);

        if(q == 0){
            V[++ N][0] = v;
            P[N][0] = p;
        }else{
            if(V[q][1] == 0){
                V[q][1] = v;
                P[q][1] = p;
            }else{
                V[q][2] = v;
                P[q][2] = p;
            }
        }
    }

    for(int i = 1;i <= N;i ++)
    {
        for(int j = n;j >= V[i][0] && V[i][0];j -= 10)
        {
            dp[j] = max(dp[j],dp[j - V[i][0]] + V[i][0] * P[i][0]);
//          printf("dp[%d] = %d\n",j,dp[j]);

            if(V[i][1] && j >= V[i][0] + V[i][1]){
                dp[j] = max(dp[j],dp[j - V[i][0] - V[i][1]] + V[i][0]  * P[i][0]+ V[i][1] * P[i][1]);
            }
            if(V[i][2] && j >= V[i][0] + V[i][2]){

                dp[j] = max(dp[j],dp[j - V[i][0] - V[i][2]] + V[i][0]  * P[i][0]+ V[i][2] * P[i][2]);
            }
            if(V[i][2] && V[i][1] && j >= V[i][0] + V[i][1] + V[i][2]){

                dp[j] = max(dp[j],dp[j - V[i][0] - V[i][1] - V[i][2]] + V[i][0]  * P[i][0]+ V[i][1] * P[i][1] + V[i][2] * P[i][2]);
            }

        }
    }

    printf("%d",dp[n]);

    return 0;
}

正确代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,N;
int V[150][3],P[150][3];
int dp[32005];

int main()
{
    scanf("%d%d",&n,&m);

    int v,p,q;
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d%d%d",&v,&p,&q);

        if(q == 0){
            V[i][0] = v;
            P[i][0] = p;
        }else{
            if(V[q][1] == 0){
                V[q][1] = v;
                P[q][1] = p;
            }else{
                V[q][2] = v;
                P[q][2] = p;
            }
        }
    }

    for(int i = 1;i <= m;i ++)
    {
        for(int j = n;j >= V[i][0] && V[i][0];j -= 10)
        {
            dp[j] = max(dp[j],dp[j - V[i][0]] + V[i][0] * P[i][0]);
//          printf("dp[%d] = %d\n",j,dp[j]);

            if(V[i][1] && j >= V[i][0] + V[i][1]){
                dp[j] = max(dp[j],dp[j - V[i][0] - V[i][1]] + V[i][0]  * P[i][0]+ V[i][1] * P[i][1]);
            }
            if(V[i][2] && j >= V[i][0] + V[i][2]){

                dp[j] = max(dp[j],dp[j - V[i][0] - V[i][2]] + V[i][0]  * P[i][0]+ V[i][2] * P[i][2]);
            }
            if(V[i][2] && V[i][1] && j >= V[i][0] + V[i][1] + V[i][2]){

                dp[j] = max(dp[j],dp[j - V[i][0] - V[i][1] - V[i][2]] + V[i][0]  * P[i][0]+ V[i][1] * P[i][1] + V[i][2] * P[i][2]);
            }

        }
    }

    printf("%d",dp[n]);

    return 0;
}

就是输入的部分改一下