20分求大神帮助!!!(1&10)

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

刘心远 @ 2017-03-17 19:50:48

#include<iostream>
using namespace std;
struct mainthing{int mainnum,items,item1,item2; };
int maxx(int a,int b){return a>b?a:b;};
int main()
{
    int money,n,i,j,k,it1,it2,maintot=0; cin>>money>>n;
    mainthing ma_in[61]; int v[61],p[61],f[32000],q;
    for(i=0;i<=money;i++)f[i]=0;
    for(i=1;i<=n;i++)
    {
        cin>>v[i]>>p[i]>>q; //其数据
        if(q==0) //是主件
        {
            ma_in[++maintot].mainnum=i; //新建主件,主件数+1
            ma_in[maintot].items=0; //附件数归0
            ma_in[maintot].item1=ma_in[maintot].item2=0; //默认无附件
        }
        else //是附件
        {
            ma_in[q].items++; //多一个附件
            if(ma_in[q].items==1)ma_in[q].item1=i; //新建附件
            else ma_in[q].item2=i;
        }
    }
    for(i=1;i<=maintot;i++) //所有主件
    for(j=money;j>=v[ma_in[i].mainnum];j--) //01背包
    {
        k=ma_in[i].mainnum; it1=ma_in[i].item1; it2=ma_in[i].item2;
        switch(ma_in[i].items) //确定附件数
        {
            case 0:f[j]=maxx(f[j],f[j-v[k]]+v[k]*p[k]); break; //无附件,仅选主件
            case 1:f[j]=maxx(f[j],f[j-v[k]]+v[k]*p[k]); //不选附件
                   if(j>=v[k]+v[it1])f[j]=maxx(f[j],f[j-v[k]-v[it1]]+v[k]*p[k]+v[it1]*p[it1]);
                   break;
            case 2:f[j]=maxx(f[j],f[j-v[k]]+v[k]*p[k]);
                   if(j>=v[k]+v[it1])f[j]=maxx(f[j],f[j-v[k]-v[it1]]+v[k]*p[k]+v[it1]*p[it1]);
                   if(j>=v[k]+v[it2])f[j]=maxx(f[j],f[j-v[k]-v[it2]]+v[k]*p[k]+v[it2]*p[it2]);
                   if(j>=v[k]+v[it1]+v[it2])f[j]=maxx(f[j],f[j-v[k]-v[it1]-v[it2]]+v[k]*p[k]+v[it1]*p[it1]+v[it2]*p[it2]);
                   break;
        }
    }
    cout<<f[money]<<endl; return 0;
}

|