Girls Band Party(2019银川A题)

链接:https://nanti.jisuanke.com/t/42381
题意:给定多个物品,每个物品有name,color,power值,然后选取五件名字不同的五件物品,使power总和最大,然后下面还有奖励机制,给定五个名字和一个颜色,如果选择的五个物品某个物品在奖励名字里,其power总和值增加10%,如果颜色值在增加20%
题解:分组背包,把名字相同的分为一组,然后把五件物品当作第一变化量,每个的奖励百分比当作第二变化量

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

const int maxn = 1e5 + 7;

map<string,int>mp1,mp2;
int dp[maxn][6][16];

struct Node
{
    int val,num;
    string name,color;
    bool operator < (const Node&rhs)const
    {
        return name < rhs.name;
    }
}a[maxn];

vector<Node>G[maxn];

void init(int n)
{
    memset(dp,-1,sizeof(dp));
    mp1.clear();mp2.clear();
    for(int i = 1;i <= n;i++)G[i].clear();
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        init(n);
        for(int i = 1;i <= n;i++)
        {
            cin >> a[i].name >> a[i].color >> a[i].val;
        }

        string tmp;
        for(int i = 1;i <= 5;i++)
        {
            cin >> tmp;mp1[tmp] = 1;
        }
        cin >> tmp;mp2[tmp] = 2;

        sort(a + 1,a + 1 + n);
        int cnt = 0;
        for(int i = 1;i <= n;i++)
        {
            if(a[i].name != a[i - 1].name)
            {
                cnt++;
            }
            a[i].num = mp1[a[i].name] + mp2[a[i].color];
            G[cnt].push_back(a[i]);
        }

        dp[0][0][0] = 0;
        for(int i = 1;i <= cnt;i++)
        {
            for(int k = 0;k <= 5;k++)
            {
                for(int q = 0;q <= 15;q++)
                {
                    dp[i][k][q] = dp[i - 1][k][q];
                }
            }
            for(int j = 0;j < G[i].size();j++)
            {
                int val = G[i][j].val,num = G[i][j].num;

                for(int k = 1;k <= 5;k++)
                {
                    for(int q = num;q <= 15;q++)
                    {
                        if(dp[i - 1][k - 1][q - num] != -1)
                        {
                            dp[i][k][q] = max(dp[i][k][q],dp[i - 1][k - 1][q - num] + val);
                        }
                    }
                }
            }
        }

        int ans = 0;
        for(int i = 0;i <= 5;i++)
        {
            for(int j = 0;j <= 15;j++)
            {
                ans = max(ans,dp[cnt][i][j] * (10 + j) / 10);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}