60分求助，WA on #3 #7 #8 #9

stswkl @ 2023-07-24 12:30:50

#include<bits/stdc++.h>
using namespace std;
const int N=32005,M=65;
int n,m,k,a[M][3],b[M][3],c,dp[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[++k][0]>>b[k][0]>>c;
        if(c!=0)
        {
            if(b[c][1]==0)
                a[c][1]=a[k][0],b[c][1]=b[k][0];
            else a[c][2]=a[k][0],b[c][2]=b[k][0];
            k--;
        }
    }
    for(int i=1;i<=k;i++)
    for(int j=n;j>=a[i][0];j--)
    {
        dp[j]=max(dp[j],dp[j-a[i][0]]+b[i][0]*a[i][0]);
        if(b[i][1]!=0&&j>=a[i][0]+a[i][1])
            dp[j]=max(dp[j],dp[j-a[i][0]-a[i][1]]+b[i][0]*a[i][0]+b[i][1]*a[i][1]);
        if(b[i][2]!=0&&j>=a[i][0]+a[i][2])
            dp[j]=max(dp[j],dp[j-a[i][0]-a[i][2]]+b[i][0]*a[i][0]+b[i][2]*a[i][2]);
        if(b[i][1]!=0&&b[i][2]!=0&&j>=a[i][0]+a[i][1]+a[i][2])
            dp[j]=max(dp[j],dp[j-a[i][0]-a[i][1]-a[i][2]]+b[i][0]*a[i][0]+b[i][1]*a[i][1]+b[i][2]*a[i][2]);
    }
    cout<<dp[n];
    return 0;
}

by ikun_newperson @ 2023-07-26 14:27:46

#include<bits/stdc++.h>
using namespace std;
int v[100005],p[100005],q[100005],w[100005];
struct abc{
    int v,w;
}P[100005][4];
int dp[100005];
int n,m,ans=-1;
void spe(){
    for(int i=1;i<=m;i++){
            if(dp[i]==i){
                P[dp[i]][1].w=w[i];
                P[dp[i]][1].v=v[i];
            }else {
                P[dp[i]][++P[dp[i]][0].v].v=v[i];
                P[dp[i]][P[dp[i]][0].v].w=w[i];
            }

    }

    return ;
}
int main(){ 
    memset(v,0,sizeof(v));memset(p,0,sizeof(p));memset(q,0,sizeof(q));memset(w,0,sizeof(w));
    cin>>n>>m;  
    for(int i=1;i<=m;i++) P[i][0].v=1;
    for(int i=1;i<=m;++i){      
        cin>>v[i]>>p[i]>>dp[i];
        if(dp[i]==0) dp[i]=i; 
        w[i]=p[i]*v[i];
    }
    spe();
    for(int i=1;i<=m;i++){
        for(int j=n;j>=0;j--){
            if(j-P[i] [1].v>=0){                
                dp[j]=max(dp[j],dp[j-P[i][1].v]+P[i][1].w);
            }
            if(j-P[i][1].v-P[i][2].v>=0){
                dp[j]=max(dp[j],dp[j-P[i][1].v-P[i][2].v]+P[i][1].w+P[i][2].w);
            }
            if(j-P[i][1].v-P[i][3].v>=0){
                dp[j]=max(dp[j],dp[j-P[i][1].v-P[i][3].v]+P[i][1].w+P[i][3].w);
            }
            if(j-P[i][1].v-P[i][2].v-P[i][3].v>=0){
                dp[j]=max(dp[j],dp[j-P[i][1].v-P[i][2].v-P[i][3].v]+P[i][1].w+P[i][2].w+P[i][3].w);
            }
        }
    }
    cout<<dp[n];
    return 0;   
}