求大佬看看,有一个点没过

P1064 [NOIP2006 提高组] 金明的预算方案

aaaaaagf @ 2023-08-07 15:05:58

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
typedef unsigned long long ULL;
typedef pair<long long,int> PLI;
int n,m;
LL f[70],fw[40000][3],fv[40000][3];//fw代表附件的钱,fv代表附件的价值
struct{
    LL a,b;
}sz[70];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int q,w,e;
        cin>>q>>w>>e;
        if(!e){
            sz[i].a=q;
            sz[i].b=w*q;
        }
        else{
            fw[e][0]++;//记录附件个数
            fw[e][fw[e][0]]=q;
            fv[e][fw[e][0]]=q*w;
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=n;j>=sz[i].a;j--){
            f[j]=max(f[j],f[j-sz[i].a]+sz[i].b);//只选主件或不选
            if(j>=sz[i].a+fw[i][1]) f[j]=max(f[j],f[j-sz[i].a-fw[i][1]]+sz[i].b+fv[i][1]);//只选主件和附件1或不选
            if(j>=sz[i].a+fw[i][2]) f[j]=max(f[j],f[j-sz[i].a-fw[i][2]]+sz[i].b+fv[i][2]);//只选主件和附件2或不选
            if(j>=sz[i].a+fw[i][1]+fw[i][2]) f[j]=max(f[j],f[j-sz[i].a-fw[i][2]-fw[i][1]]+sz[i].b+fv[i][2]+fv[i][1]);//都选或者都不选
        }
    }
    cout<<f[n];
    return 0;
}

|