#4Wa求调

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

halehu @ 2022-07-18 21:19:40

调崩了,答案是16700,一直输出16500

#include<iostream>
using namespace std;
int f[65][40005],i,j,n,tot=1,m,v,p,q;
struct node{
    int t,v0,p0,v1,p1,v2,p2,qq;
}w[65];
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>v>>p>>q;
        if(q==0){
            w[tot].p0=p,w[tot].v0=v;
            w[tot].qq=i,w[tot++].t=1;
        }
        else{
            for(j=tot-1;j>=1;j--){
                if(w[j].qq==q){
                    if(w[j].t==1)w[j].v1=v,w[j].p1=p,w[j].t++;
                    else w[j].v2=v,w[j].p2=p,w[j].t++;
                    break;
                }
            }
        }
    }
    for(i=1;i<tot;i++){
        for(j=1;j<=n;j++){
            if(j>=w[i].v0)f[i][j]=max(f[i-1][j-w[i].v0]+w[i].v0*w[i].p0,f[i-1][j]);
            if(j>=w[i].v0+w[i].v1)
               f[i][j]=max(f[i][j],f[i-1][j-w[i].v0-w[i].v1]+w[i].v0*w[i].p0+w[i].v1*w[i].p1);
            if(j>=w[i].v0+w[i].v2)
                f[i][j]=max(f[i][j],f[i-1][j-w[i].v0-w[i].v2]+w[i].v0*w[i].p0+w[i].p2*w[i].v2);
            if(j>=w[i].v0+w[i].v1+w[i].v2)
                f[i][j]=max(f[i][j],f[i-1][j-w[i].v0-w[i].v1-w[i].v2]+w[i].v0*w[i].p0+w[i].p1*w[i].v1+w[i].p2*w[i].v2);
        }
    }
    cout<<f[tot-1][n]<<endl;
}

|