为什么我80分？

13813812138xixixixi @ 2017-10-15 15:34:28

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[5000000];
struct kk{
    int num,cost,ipc,s;
}a[1000][5];
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        int v,p,q;
        scanf("%d%d%d",&v,&p,&q);
        a[i][0].cost=v;
        a[i][0].ipc=p;
        a[i][0].s=p*v;
        if(!q)a[q][0].num=0;
            else {
                    a[i][0].num=-1;
                    a[q][0].num++;
                    a[q][a[q][0].num].cost=v;
                    a[q][a[q][0].num].ipc=p;
                    a[q][a[q][0].num].s=v*p;
                }
    }
    for(int i=1;i<=n;i++){
        if(a[i][0].num==-1)continue;
        for(int j=m;j>=a[i][0].cost;j-=10){
            if(f[j-a[i][0].cost]+a[i][0].s>f[j])f[j]=f[j-a[i][0].cost]+a[i][0].s;
            for(int k=1;k<=a[i][0].num;k++){
                if(j>a[i][0].cost+a[i][k].cost
                    &&f[j-a[i][0].cost-a[i][k].cost]+a[i][0].s+a[i][k].s>f[j])f[j]=
                    f[j-a[i][0].cost-a[i][k].cost]+a[i][0].s+a[i][k].s;
            }
            if(a[i][0].num==2&&j>a[i][0].cost+a[i][1].cost+a[i][2].cost

        a[i][0].s+a[i][1].s+a[i][2].s;
        //printf("%d ",f[m]);
        }
    //    printf("\n");
    }
    printf("%d\n",f[m]);
    return 0;
}

by 超威蓝猫 @ 2017-10-15 15:47:47

因为你错了20分

by 13813812138xixixixi @ 2017-10-16 13:19:52

for(int i=1;i<=n;i++){

改成for(int i=n;i>=1;i--){就过了

by Kamilavalieva26 @ 2018-08-03 20:53:29

@13813812138xixixixi 哇，真的，本来我也80，这么一改就过了。太感谢了。 dalao求教，到底是为什么呢？ 这是我的AC代码。

#include <bits/stdc++.h>
using namespace std;

struct NODE{
    int vv, ww;
}fj[65][5];
int f[32010], cnt[65], bh[65], v[65], w[65], tot, n, m;

int main(){
    cin>>n>>m;
    for (int i=1; i<=m; i++){
        int c, p, q;
        cin>>c>>p>>q;
        if (q==0){
            tot++;
            v[tot]=c;
            w[tot]=c*p;
            bh[i]=tot;
        }
        else{
            int t=bh[q];
            cnt[t]++;
            fj[t][cnt[t]].vv=c;
            fj[t][cnt[t]].ww=c*p;
        }
    }

    for (int i=tot; i>=1; i--)
        for (int j=n; j>=v[i]; j--){
            f[j]=max(f[j], f[j-v[i]]+w[i]);
            if (cnt[i]){
                if (j>v[i]+fj[i][1].vv)
                    f[j]=max(f[j], f[j-v[i]-fj[i][1].vv]+w[i]+fj[i][1].ww);
                if (cnt[i]==2){
                    if (j>v[i]+fj[i][2].vv)
                        f[j]=max(f[j], f[j-v[i]-fj[i][2].vv]+w[i]+fj[i][2].ww);
                    if (j>v[i]+fj[i][1].vv+fj[i][2].vv)
                        f[j]=max(f[j], f[j-v[i]-fj[i][1].vv-fj[i][2].vv]+w[i]+fj[i][1].ww+fj[i][2].ww);
                }
            }
        }

    cout<<f[n]<<endl;

    return 0;
}