60求助 ！！WA 3 7 8 9

small_C_77777 @ 2022-05-01 15:21:37

#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[32001];
struct node{
    int v,s;
};
node mit[61][5];//1-00;2-10;3-01;4-11;
node fit[61][3];
int fn[61];
int main()
{
    cin>>n>>m;
    int k=1;//组号 
    for(int i=1;i<=m;i++)
    {
        node t;
        int imp,g;//所属组数 
        cin>>t.v>>imp>>g;//临时储存 
        t.s=t.v*imp;
        if(g==0)//新的组 
        {
            for(int j=1;j<=4;j++)
            {mit[k][j]=t;} 
            k+=1;
        }
        else//附件
        {
            fn[g]+=1; 
            fit[g][fn[g]]=t;//存储附件1与2
        }
    }
    for(int g=1;g<k;g++)
    {
        if(fn[g])
        {
            mit[g][2].v+=fit[g][1].v;
            mit[g][2].s+=fit[g][1].s;
        }
        if(fn[g]==2)
        {
            mit[g][3].v+=fit[g][2].v;
            mit[g][3].s+=fit[g][2].s;
            mit[g][4].v+=fit[g][1].v+fit[g][2].v;
            mit[g][4].s+=fit[g][1].s+fit[g][2].s;
        }
    }
    //1-00;2-10;3-01;4-11;
    //cout<<k<<"\n";
    /*
    for(int i=1;i<k;i++)
    {
        for(int g=1;g<=4;g++)
            {
                cout<<mit[i][g].v<<" "<<mit[i][g].s<<"\n";
            }
        cout<<"\n";
    }
    */
    for(int i=1;i<k;i++)
    {
        for(int j=n;j>=0;j--)
        {
            for(int g=1;g<=4;g++)
            {
                if(j>=mit[i][g].v)
                dp[j]=max(dp[j],dp[j-mit[i][g].v]+mit[i][g].s);
            }
        }
    }
    /*for(int i=1;i<=n;i++)
    cout<<i<<" "<<dp[i]<<"\n";*/
    cout<<dp[n];
}

by small_C_77777 @ 2022-05-01 15:22:26

感觉就是分组，分组也已经分好了，但是不知道为什么最后遍历完就错了

by zo__Oz @ 2022-06-06 23:00:51

https://www.luogu.com.cn/discuss/402676 这个应该能帮到你。 这是我的代码。 我原来也是这几个点错。原因见链接。 主要是输入时对编号理解错误

#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;
}