蒟蒻求助。。。

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

IRipple @ 2018-07-16 11:24:27

orz不知道哪里错了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,chose[100],f[100][40000];
struct zwhakioi{
    int val,imp,son0,son1,ff;
}a[40000];
int main(){
    cin>>n>>m;
    int q; 
    for(int i=1;i<=m;i++){
        cin>>a[i].val>>a[i].imp>>q;
        a[i].imp*=a[i].val;
        if(q){
            a[i].ff=1;
            if(a[q].son0) a[q].son1=i;
            else a[q].son0=i;
        }
    }
    for(int i=1;i<=m;i++){
        if(a[i].ff) continue;
        for(int j=n;j>=0;j-=100){
            int v=a[i].val,vv=a[i].imp;
            int s1=a[i].son0,v1=a[s1].val,vv1=a[s1].imp;
            int s2=a[i].son1,v2=a[s2].val,vv2=a[s2].imp;
            if(j>=v){
                f[i][j]=max(f[i-1][j],f[i-1][j-v]+vv);
                if(j>=v+v1) f[i][j]=max(f[i][j],f[i-1][j-v-v1]+vv+vv1);
                if(j>=v+v2) f[i][j]=max(f[i][j],f[i-1][j-v-v2]+vv+vv2);
                if(j>=v+v1+v2) f[i][j]=max(f[i][j],f[i-1][j-v-v1-v2]+vv+vv1+vv2);
            }
            if(j<v) f[i][j]=f[i-1][j];
            cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
        }   
    }
    cout<<f[m][n];
    return 0;
}

by 人殇物已非 @ 2018-07-16 11:33:56

您太强了,震慑了测评姬


by TianZ @ 2018-08-02 18:54:01

@恣扬_Elite

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,chose[100],f[100][40000];
struct zwhakioi{
    int val,imp,son0,son1,ff;
}a[40000];
int main(){
    cin>>n>>m;
    int q; 
    for(int i=1;i<=m;i++){
        cin>>a[i].val>>a[i].imp>>q;
        a[i].imp*=a[i].val;
        if(q){
            a[i].ff=1;
            if(a[q].son0) a[q].son1=i;
            else a[q].son0=i;
        }
    }
    for(int i=1;i<=m;i++){
        if(a[i].ff) continue;
        for(int j=n;j>=0;j-=100){
            int v=a[i].val,vv=a[i].imp;
            int s1=a[i].son0,v1=a[s1].val,vv1=a[s1].imp;
            int s2=a[i].son1,v2=a[s2].val,vv2=a[s2].imp;
            if(j>=v){
                f[i][j]=max(f[i-1][j],f[i-1][j-v]+vv);
                if(j>=v+v1) {f[i][j]=max(f[i][j],f[i-1][j-v-v1]+vv+vv1);continue;}
                if(j>=v+v2) {f[i][j]=max(f[i][j],f[i-1][j-v-v2]+vv+vv2);continue;}
                if(j>=v+v1+v2) {f[i][j]=max(f[i][j],f[i-1][j-v-v1-v2]+vv+vv1+vv2);continue;}
            }
                if(j<v) f[i][j]=f[i-1][j];continue;
            cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
        }   
    }
    cout<<f[m][n];
    return 0;
}
//在你的源代码上改动一下哦

|