60!改不出来错

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

zz4477 @ 2018-11-07 21:35:28

#include<iostream>
#include<cstdlib>
using namespace std;
int f[1000000];
int sum=0;
int p[800][3],v[800][3];
int main()
{
    int n,m,a,b,c;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        if(!c)
        {           
            p[++sum][0]=a/10;
            v[sum][0]=a*b;
        }
        else 
        {
            if(!p[c][1])
            {
                p[c][1]=a/10;
                v[c][1]=a*b;
            }
            else 
            {
                p[c][2]=a/10;
                v[c][2]=a*b;
            }
        }
        //system("pause");
    }
    n/=10;
/*  for(int i=1;i<=sum;i++)
    {
        cout<<p[i][0]<<" "<<p[i][1]<<" "<<p[i][2]<<endl;
        cout<<v[i][0]<<" "<<v[i][1]<<" "<<v[i][2]<<endl;
    }*/
    for(int i=1;i<=sum;i++)
    {
        for(int j=n;j>=p[i][0];j--)
        {
            if(j>=p[i][0]) f[j]=max(f[j],f[j-p[i][0]]+v[i][0]);
            if(j>=p[i][0]+p[i][1]) f[j]=max(f[j],f[j-p[i][0]-p[i][1]]+v[i][0]+v[i][1]);
            if(j>=p[i][0]+p[i][2]) f[j]=max(f[j],f[j-p[i][0]-p[i][2]]+v[i][0]+v[i][2]);
            if(j>=p[i][1]+p[i][2]+p[i][0]) f[j]=max(f[j],f[j-p[i][0]-p[i][2]-p[i][1]]+v[i][0]+v[i][2]+v[i][1]);
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

by zz4477 @ 2018-11-08 07:15:13

@礼弥酱 谢谢大佬!!!


by 学习小能手 @ 2019-05-08 11:31:00

@limi_sanhua 谢谢大佬


上一页 |