2020-08-13

http://icpc.upc.edu.cn/problem.php?id=16535

题目

16535: Lead of Wisdom

题目描述

In an online game, "Lead of Wisdom" is a place where the lucky player can randomly get powerful items.

There are k types of items, a player can wear at most one item for each type. For the i-th item, it has four attributes ai,bi,ci and di. Assume the set of items that the player wearing is S, the damage rate of the player DMG can be calculated by the formula:

Little Q has got n items from "Lead of Wisdom", please write a program to help him select which items to wear such that the value of DMG is maximized.

输入

The first line of the input contains a single integer T (1≤T≤10), the number of test cases.

For each case, the first line of the input contains two integers n and k (1≤n,k≤50), denoting the number of items and the number of item types.

Each of the following n lines contains five integers ti,ai,bi,ci and di (1≤ti≤k, 0≤ai,bi,ci,di≤100), denoting an item of type ti whose attributes are ai,bi,ci and di.

输出

For each test case, output a single line containing an integer, the maximum value of DMG.

样例输入

1
6 4
1 17 25 10 0
2 0 0 25 14
4 17 0 21 0
1 5 22 0 10
2 0 16 20 0
4 37 0 0 0

样例输出

297882000

暴力搜索即可

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    int a,b,c,d;
};
vector<node>w[60];
int t,n,k,a,b,c,d,e;
int cnt=0;
ll max1=0;
map<int,int>mp;
inline int q(register int p,register int sum1,register int sum2,register int sum3,register int sum4)
{
    if(p==cnt+1)
    {
        max1=max(max1,(ll)sum1*sum2*sum3*sum4);
        return 0;
    }
    if(w[p].empty())
        q(p+1,sum1,sum2,sum3,sum4);
    else
        for(register int i=0; i<w[p].size(); i++)
        {
            q(p+1,sum1+w[p][i].a,sum2+w[p][i].b,sum3+w[p][i].c,sum4+w[p][i].d);
        }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        max1=0;
        scanf("%d%d",&n,&k);
        for(register int i=1; i<=k; i++)
            w[i].clear();
        mp.clear();
        cnt=0;
        for(register int i=1; i<=n; i++)
        {
            scanf("%d%d%d%d%d",&e,&a,&b,&c,&d);
            if(mp[e]==0)
            {
                mp[e]=++cnt;
            }
            w[mp[e]].push_back({a,b,c,d});
        }
        q(1,100,100,100,100);
        printf("%lld\n",max1);
    }
}