第二个点莫名WA求调

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

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.初始化方式不对,无法应对附件在主件前的情况。


|