我的代码是不是还漏了什么呢?只有60分?

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

lako @ 2016-12-09 22:44:58

#include<iostream>
#include<cstdio>
using namespace std;

int n,m;
int v[1000],p[1000];
int vq[100][10];
int pq[100][10];
int num[1000];
int f[40000];
#define max(a,b) (((a)>(b))?(a):(b))
int main(){
    //freopen("testdata.in","r",stdin);
    cin>>n>>m;
    int qq;
    int a,b;
    int mm=0;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>qq;
        if(qq==0){
            mm++;
            v[mm]=a;
            p[mm]=b;
        }
        else{
            num[qq]++;
            vq[qq][num[qq]]=a;
            pq[qq][num[qq]]=b;
        }
    }
    for(int i=1;i<=mm;i++){
        for(int j=n;j>=0;j--){
            if(j>=v[i])    f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);
            if(j>=v[i]+vq[i][1])f[j]=max(f[j],f[j-v[i]-vq[i][1]]+v[i]*p[i]+vq[i][1]*pq[i][1]);
            if(j>=v[i]+vq[i][2])f[j]=max(f[j],f[j-v[i]-vq[i][2]]+v[i]*p[i]+vq[i][2]*pq[i][2]);
            if(j>=v[i]+vq[i][1]+vq[i][2])f[j]=max(f[j],f[j-v[i]-vq[i][1]-vq[i][2]]+v[i]*p[i]+vq[i][1]*pq[i][1]+vq[i][2]*pq[i][2]);
        }
    }
    cout<<f[n];
    return 0;
}

by lako @ 2016-12-10 00:18:41

问题解决了,是我的变量绑定物品编号不对。改成这样

for(int i=1;i<=m;i++){
        cin>>a>>b>>qq;
        if(qq==0){
            v[i]=a;
            p[i]=b*a;
        }
        else{
            num[qq]++;
            vq[qq][num[qq]]=a;
            pq[qq][num[qq]]=b*a;
        }
    }

这样就对了,惨痛的教训


|