题解 | #牛牛的背包#

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct commodity
{
    int type;
    int taste;
    int flag;
}com[55];
int n;
void check(int j)
{
    for(int i=0;i<n;i++)
    {
        if(com[i].type==com[j].type)
            com[i].flag=1;
    }
}
int cmp(commodity com1,commodity com2)
{
    return com1.taste<com2.taste;
} 
int main()
{
    int j;
    memset(com,0,sizeof(commodity)*55);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>com[i].type;
    for(int i=0;i<n;i++)
        cin>>com[i].taste;
    sort(com,com+n,cmp);
    for(int i=0;i<n;i++)
    {
        if(com[i].taste>=0)
        {
             j=i;
            break;
        }
    }
    int x=0,y=0;
    for(int i=j;i<n;i++)
    {
        if(com[i].flag==0)
        {
            x++;
            check(i);
        }
        y+=com[i].taste;
    }
    long long ans,temp=0;
    ans=x*y;
    for(int i=j-1;i>=0;i--)
    {
        int x1,y1;
        x1=x;y1=y;
        if(com[i].flag==0)
        {
            x1++;
            check(i);
        }
        y1+=com[i].taste;
        temp=x1*y1;
        if(temp>ans)
        {
            ans=temp;
            x=x1;
            y=y1;
        }
    }
    cout<<ans;
    return 0;
}