大佬们啊!!!90分怎么破???

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

Dont_talk_any_more @ 2017-11-04 18:37:47

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define e 66
using namespace std;
int n,m;
int f[60000];
int pricezhu[e],pricefu[e][3],importancezhu[e],importancefu[e][3];
int main(){
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        if(c==0)
            pricezhu[i]=a,importancezhu[i]=a*b;
        else if(c>0){
            pricefu[c][0]++;
            pricefu[c][pricefu[c][0]]=a,importancefu[c][pricefu[c][0]]=a*b;
        }
    }
    for(int i=m;i>=1;i--)
    for(int j=n;pricezhu[i]!=0&&j>=pricezhu[i];j--){
            if(j>=pricezhu[i]+pricefu[i][1])
   f[j]=max(f[j],f[j-pricezhu[i]-pricefu[i][1]]+importancezhu[i]+importancefu[i][1]);
            if(j>=pricezhu[i]+pricefu[i][2])
   f[j]=max(f[j],f[j-pricezhu[i]-pricefu[i][2]]+importancezhu[i]+importancefu[i][2]);
            if(j>=pricezhu[i]+pricefu[i][1]+pricefu[i][2])
                f[j]=max(f[j],f[j-pricezhu[i]-pricefu[i][1]-pricefu[i][2]]+importancezhu[i]+importancefu[i][1]+importancefu[i][2]);
   }
    cout<<f[n]<<endl;
    return 0;
}

|