90分求调Wa #5

hzb1121 @ 2024-07-09 20:40:02

#include<iostream>
using namespace std;
int n,m,ans;
struct object{
    int v;
    int p;
    int q;
    int s1;
    int s2;
}a[65];
int f[65][32005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].v>>a[i].p>>a[i].q;
        if(a[i].q!=0){
            if(a[a[i].q].s1==0) a[a[i].q].s1=i;
            else a[a[i].q].s2=i;
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i].q==0){
                int s1=a[i].s1,s2=a[i].s2;
                if(j-a[i].v-a[s1].v>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s1].v]+a[i].p*a[i].v+a[s1].p*a[s1].v);
                if(j-a[i].v-a[s2].v>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s2].v]+a[i].p*a[i].v+a[s2].p*a[s2].v);
                if(j-a[i].v-a[s1].v-a[s2].v>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s1].v-a[s2].v]+a[i].p*a[i].v+a[s1].p*a[s1].v+a[s2].p*a[s2].v);
            }
        }
    }
    cout<<f[m][n];
    return 0;
}

by cxjy @ 2024-07-13 14:09:25

存在有附件但是不买附件的情况

#include<iostream>
using namespace std;
int n,m,ans;
struct object{
    int v;
    int p;
    int q;
    int s1;
    int s2;
}a[65];
int f[65][32005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].v>>a[i].p>>a[i].q;
        if(a[i].q!=0){
            if(a[a[i].q].s1==0) a[a[i].q].s1=i;
            else a[a[i].q].s2=i;
        }

    }
    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=0;j--)
        {
            f[i][j]=f[i-1][j];
            if(a[i].q==0){
                int s1=a[i].s1,s2=a[i].s2;
                if(j-a[i].v>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].v]+a[i].p*a[i].v);
                if(j-a[i].v-a[s1].v>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s1].v]+a[i].p*a[i].v+a[s1].p*a[s1].v);
                if(j-a[i].v-a[s2].v>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s2].v]+a[i].p*a[i].v+a[s2].p*a[s2].v);
                if(j-a[i].v-a[s1].v-a[s2].v>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].v-a[s1].v-a[s2].v]+a[i].p*a[i].v+a[s1].p*a[s1].v+a[s2].p*a[s2].v);
            }
        }
    }
    cout<<f[m][n];
    return 0;
}