10分 求助

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

Arusu @ 2018-09-05 19:37:45

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define MAXN 33333
using namespace std;
int n,m,v[MAXN],p[MAXN],q[MAXN],f[MAXN],ok[MAXN]={};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v[i]>>p[i]>>q[i];
        p[i]*=v[i];
    }
    for(int i=1;i<=m;i++)
    for(int j=n;j>=v[i];j--)
    {
        if(j>v[i]&&q[i]==0)
        {
            f[j]=max(f[j],f[j-v[i]]+p[i]);
            ok[MAXN]++;
        }
        if(j>v[i]&&q[i]!=0&&ok[q[i]]!=0)
        f[j]=max(f[j],f[j-v[i]]+p[i]);
    }
    cout<<f[n]<<endl;
    return 0;
} 

by cnyali_hjh @ 2018-09-05 19:41:53

@l_y_y 做法好像有问题,每个主件可以有0个、1个或2个附件。


|