CC__DIAMOND @ 2024-03-29 23:36:20
第二个点输出了7200,一直和正解对不上,没找到bug.求dalao帮助。
#include <bits/stdc++.h>
#define PBAR cout<<"*******\n";
#define fst first
#define snd second
using namespace std;
using ll=long long;
using ul=unsigned long long;
using ui=unsigned int;
using db=double;
#define INFILE(x) freopen(x,"r",stdin)
#define OUTFILE(x) freopen(x,"w",stdout)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
const int maxn=3.2e4+10;
const int maxm=70;
int n,m,t;
struct Item{
int c,v[4],y[4];
} items[maxm];
int f[maxn],x[3]={1,2,4};
int main(){
ios::sync_with_stdio(0); cin.tie(0);
INFILE("IOFile/P1064_2.in");
cin>>n>>m;
for(int i=1;i<=m;++i){
int v,p,q;
cin>>v>>p>>q;
if(!q){
items[++t]={0,{v,v,v,v},{v*p,v*p,v*p,v*p}};
}else{
auto &item=items[q]; item.c++;
if(item.c){
item.v[2]+=v; item.v[3]+=v;
item.y[2]+=v*p; item.y[3]+=v*p;
}else{
item.v[1]+=v; item.v[3]+=v;
item.y[1]+=v*p; item.y[3]+=v*p;
}
}
}
for(int i=1;i<=t;++i){
auto &item=items[i];
for(int j=n;j>=item.v[0];--j){
for(int k=0;k<x[item.c];++k){
if(j-item.v[k]<0)continue;
f[j]=max(f[j],f[j-item.v[k]]+item.y[k]);
}
}
}
cout<<f[n]<<'\n';
return 0;
}
by CC__DIAMOND @ 2024-03-29 23:57:47
WA原因有三: 1.没有给附件在items里留空位,导致q的下标和实际无法对应。 2.item.c++应该写在ifelse后面。 3.初始化方式不对,无法应对附件在主件前的情况。