80分求调

protractor @ 2023-08-20 22:14:29

by xiao__xiao @ 2023-08-23 11:09:08

@lijinhan_bmx 您将双重for循环内的五个是否选择判断的>改为>=就可以过了

by xiao__xiao @ 2023-08-23 11:10:47

#include<iostream>
using namespace std;
struct wupin{
    int v,w,p1,p2,j,f;
}a[32050];
int m[32050];
int f[32050];
int main()
{
    int n,M;
    cin>>n>>M;
    for(int i=1;i<=M;i++)
    {
        int v,p,q;
        cin>>v>>p>>q;
        if(q)
        {
            a[i].f=1;
            a[i].v=v;
            a[i].w=p;
            a[q].j++;
            if(a[q].j==1)  a[q].p1=i;
            if(a[q].j==2)   a[q].p2=i;
        }
        else{
            a[i].f=0;
            a[i].v=v;
            a[i].w=p;
        }
    }
    for(int i=1;i<=M;i++)
    {
        if(a[i].f) continue;
        for(int j=n;j>=10;j-=10)
        {
            if(a[i].v<=j) f[j]=max(f[j],f[j-a[i].v]+a[i].w*a[i].v);
            int _1=a[i].p1 ,_2=a[i].p2;
            if(j-a[i].v-a[_1].v>=0) f[j]=max(f[j],f[j-a[i].v-a[_1].v]+a[i].w*a[i].v+a[_1].w*a[_1].v);
            if(j-a[i].v-a[_2].v>=0) f[j]=max(f[j],f[j-a[i].v-a[_2].v]+a[i].w*a[i].v+a[_2].w*a[_2].v);
            if(j-a[i].v-a[_1].v-a[_2].v>=0) f[j]=max(f[j],f[j-a[i].v-a[_1].v-a[_2].v]+a[i].w*a[i].v+a[_1].w*a[_1].v+a[_2].w*a[_2].v);
        }
    }
    cout<<f[n];
    return 0;
}

by xiao__xiao @ 2023-08-23 11:11:00

亲测可过

by protractor @ 2023-08-23 12:22:06

谢谢dalao，Orz