求助大佬们

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

_19992146 @ 2017-11-05 11:15:58

#include<iostream>
#include<algorithm>
using namespace std;
int f[32000];
struct stu
{
    int money;
    int product;
    int belong;
}item[61];
int main()
{
    int allmoney;
    int allnum;
    cin>>allmoney>>allnum;
    for(int i=1;i<=allnum;i++)
    {
        cin>>item[i].money>>item[i].product>>item[i].belong;
        item[i].product*=item[i].money;
    }
    for(int i=1;i<=allnum;i++)
      for(int j=allmoney,l=item[i].money+item[item[i].belong].money;j>=l;j-=10)
      {
          int l1=item[i].product+item[item[i].belong].product;
          f[j]=max(f[j],f[j-l]+l1);
      }
      cout<<f[allmoney];
}
##思路上是找不到错了。。但还是爆WA

by _19992146 @ 2017-11-07 00:07:53

#include<iostream>
#include<algorithm>
using namespace std;
int f[32000];
int allmoney;
int allnum;
int mp1[61][61];
int mp2[61];
struct stu
{
    int money;
    int product;
    int belong;
}item[61];
void deal(int i)
{
    if(item[i].belong!=0)return;
    int k=mp2[i];
    int a=0,b=0;
    if(k!=0)
      for(int j=1,l=0;l<k;j++)
      {
          if(mp1[i][j]!=0)
          {
              if(a==0)a=j;
              else b=j;
              l++;
          }
      }//cout<<a<<' '<<b<<' '<<k<<endl;
       for(int j=allmoney,l=item[i].money;j>=l;j-=10)
         {
             int l1=item[i].product;
            f[j]=max(f[j],f[j-l]+l1);
         }
     if(k==1||k==2)
    {
        for(int j=allmoney,l=item[i].money+item[a].money;j>=l;j-=10)
         {
             int l1=item[i].product+item[a].product;
            f[j]=max(f[j],f[j-l]+l1);
         }
    }
     if(k==2)
    {
        for(int j=allmoney,l=item[i].money+item[b].money;j>=l;j-=10)
         {
             int l1=item[i].product+item[b].product;
            f[j]=max(f[j],f[j-l]+l1);
         }
        for(int j=allmoney,l=item[i].money+item[a].money+item[b].money;j>=l;j-=10)
         {
             int l1=item[i].product+item[a].product+item[b].product;
            f[j]=max(f[j],f[j-l]+l1);
         }
    }
}
int main()
{
    cin>>allmoney>>allnum;
    for(int i=1;i<=allnum;i++)
    {
        cin>>item[i].money>>item[i].product>>item[i].belong;
        item[i].product*=item[i].money;
        if(item[i].belong!=0)
        {
            mp1[item[i].belong][i]++;
            mp2[item[i].belong]++;
        }
    }
    for(int i=1;i<=allnum;i++)
       deal(i);
      cout<<f[allmoney];
}//wrong

|