吐血,为啥总是改不好。。。

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

Carrot_killer @ 2018-01-16 19:48:22

求大神指点指点

上代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ff=1;
int use[100001][3];
int dp[100001];
struct node{
    int a,t,g,imp;
}p[1000001];
node an[1000001];
void create(int k){
    node q[5];
    q[1]=p[k];
    node f;
    f.a=p[k].a+p[use[k][1]].a;
    f.g=0;
    f.t=p[k].t+p[use[k][1]].t;
    f.imp=p[k].a*p[k].t+p[use[k][1]].a*p[use[k][1]].t;
    q[2]=f;
    f.a=p[k].a+p[use[k][2]].a;
    f.g=0;
    f.t=p[k].t+p[use[k][2]].t;
    f.imp=p[k].a*p[k].t+p[use[k][2]].a*p[use[k][2]].t;
    q[3]=f;
    f.a=p[k].a+p[use[k][1]].a+p[use[k][2]].a;
    f.g=0;
    f.t=p[k].t+p[use[k][1]].t+p[use[k][2]].t;
    f.imp=p[k].a*p[k].t+p[use[k][1]].a*p[use[k][1]].t+p[use[k][2]].a*p[use[k][2]].t;
    q[4]=f;
    int oh=1;
    while(oh<5){
        an[ff]=q[oh];
        oh++;
        ff++;
    }
}
void fill(int h){
    int temp=1;
    while(use[p[h].g][temp]!=0) temp++;
    use[p[h].g][temp]=h;
    use[h][0]=-1;//this one have removed!
}
int main(){
    memset(use,0,sizeof(use));
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        use[i][0]=i;
        cin>>p[i].a>>p[i].t>>p[i].g;
        p[i].imp=p[i].t*p[i].a;
        if(p[i].g!=0){
            fill(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(use[i][0]!=-1){
            if(use[i][1]==0){
            an[ff]=p[i];
            ff++;
            }
            else create(i);
        }
    }
    for(int i=1;i<=ff;i++){
        for(int j=m;j>=an[i].a;j--){
            dp[j]=max(dp[j],dp[j-an[i].a]+an[i].imp);
        }
    }   
    cout<<dp[m];
    return 0;
}

|