# 装饰珠

**题目描述**

在怪物猎人这一款游戏中，玩家可以通过给装备镶嵌不同的装饰珠来获取 相应的技能，以提升自己的战斗能力。

已知猎人身上一共有 6 件装备，每件装备可能有若干个装饰孔，每个装饰孔有各自的等级，可以镶嵌一颗小于等于自身等级的装饰珠 (也可以选择不镶嵌)。

装饰珠有 M 种，编号 1 至 M，分别对应 M 种技能，第 i 种装饰珠的等级为 $L_i$，只能镶嵌在等级大于等于 $L_i$ 的装饰孔中。

对第 i 种技能来说，当装备相应技能的装饰珠数量达到 $K_i$个时，会产生$W_i$($K_i$)的价值，镶嵌同类技能的数量越多，产生的价值越大，即$W_i$($K_{i-1}$)<$W_i$($K_i$)。但每个技能都有上限$P_i$(1≤$P_i$≤7)，当装备的珠子数量超过$P_i$时，只会产生$W_i$($P_i$)的价值。

对于给定的装备和装饰珠数据，求解如何镶嵌装饰珠，使得 6 件装备能得到的总价值达到最大。

**输入描述**

输入的第 1 至 6 行，包含 6 件装备的描述。其中第i行的第一个整数Ni表示第i件装备的装饰孔数量。后面紧接着Ni个整数，分别表示该装备上每个装饰孔的等级L(1≤ L ≤4)。

第 7 行包含一个正整数 M，表示装饰珠 (技能) 种类数量。

第 8 至 M + 7 行，每行描述一种装饰珠 (技能) 的情况。每行的前两个整数$L_j$(1≤ $L_j$ ≤4)和$P_j$(1≤ $P_j$ ≤7)分别表示第 j 种装饰珠的等级和上限。接下来$P_j$个整数，其中第 k 个数表示装备该中装饰珠数量为 k 时的价值$W_j$(k)。

其中$1 ≤ N_i ≤ 50，1 ≤ M ≤ 10^4，1 ≤ W_j(k) ≤ 10^4。$

**输出描述**

输出一行包含一个整数，表示能够得到的最大价值。

**输入**

```
1 1
2 1 2
1 1
2 2 2
1 1
1 3
3
1 5 1 2 3 5 8
2 4 2 4 8 15
3 2 5 10
```

**输出**

```
20
```

**样例说明**

按照如下方式镶嵌珠子得到最大价值 20，括号内表示镶嵌的装饰珠的种类编号：

```
1: (1)
2: (1) (2)
3: (1)
4: (2) (2)
5: (1)
6: (2)
```

4 颗技能 1 装饰珠，4 颗技能 2 装饰珠 $W_1(4) + W_2(4) = 5 + 15 = 20。W_1(4)+W_2(4)=5+15=20$。

以下<span style="color:red">错误</span>的一项是？

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
其他三个都不对
```

## 选项

### A

```c
int main()
{
    vector<int> Hole(5);
    int N, tmp, total = 0;
    for (int i = 0; i < 6; ++i)
    {
        cin >> N;
        for (int j = 0; j < N; ++j)
        {
            cin >> tmp;
            ++Hole[tmp];
            ++total;
        }
    }
    cin >> N;
    vector<int> L(N + 1);
    vector<vector<int>> W(N + 1, vector<int>());
    for (int i = 1; i <= N; ++i)
    {
        cin >> L[i];
        cin >> tmp;
        W[i].resize(tmp + 1);
        for (int j = 1; j <= tmp; ++j)
        {
            cin >> W[i][j];
        }
    }
    vector<vector<int>> dp(N + 1, vector<int>(total + 1));
    int sum = 0;
    int kind = 0;
    for (int level = 4; level >= 1; --level)
    {
        sum += Hole[level];
        if (sum == 0)
            continue;
        for (int k = 1; k <= N; ++k)
        {
            if (L[k] == level)
            {
                ++kind;

                for (int i = 1; i <= sum; ++i)
                {
                    dp[kind][i] = dp[kind - 1][i];
                }

                for (int i = 1; i < W[k].size(); ++i)
                {
                    for (int j = sum; j >= i; --j)
                    {
                        dp[kind][j] = max(dp[kind][j], dp[kind - 1][j - i] + W[k][i]);
                    }
                }
            }
        }
    }
    cout << *max_element(dp[kind].begin(), dp[kind].end()) << endl;
    return 0;
}
```

### B

```c
int Solution()
{
    int n, sum = 0, L[5] = {0}, m, M, W[5][10] = {0}, le, P, res = 0;
    for (int i = 0; i < 6; i++)
    {
        cin >> n;
        sum += n;
        for (int j = 0; j < n; j++)
        {
            cin >> m;
            L[m]++;
        }
    }
    cin >> M;
    int ww;
    for (int i = 0; i < M; i++)
    {
        cin >> le >> P;
        for (int j = 1; j <= P; j++)
        {
            cin >> ww;
            if (ww > W[le][j])
                W[le][j] = ww;
            if ((j + 1 > P) && P < 7)
                for (int k = j + 1; k <= 7; k++)
                    W[le][k] = W[le][k - 1];
        }
    }
    for (int i = 0; i <= L[4]; i++)
    {
        for (int j = 0; j <= (sum - L[1] - L[2] - i); j++)
        {
            for (int k = 0; k <= (sum - L[1] - (i + j)); k++)
            {
                for (int s = 0; s <= (sum - (i + j + k)); s++)
                {
                    int a, b, c, d;
                    if (i > 7)
                        a = 7;
                    else
                        a = i;
                    if (j > 7)
                        b = 7;
                    else
                        b = j;
                    if (k > 7)
                        c = 7;
                    else
                        c = k;
                    if (s > 7)
                        d = 7;
                    else
                        d = s;
                    res = max(res, W[4][a] + W[3][b] + W[2][c] + W[1][d]);
                }
            }
        }
    }
    return res;
}
int main()
{
    cout << Solution();
    return 0;
}

```

### C

```c
constexpr size_t MAXN = 55, MAXS = 305, MAXM = 1e4 + 5;
int n[MAXN], cnt[5], Lv[MAXM], p[MAXM], w[MAXM][MAXN];
int dp[MAXM][MAXS];
int m;

inline void Read()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (int i = 1; i <= 6; i++)
    {
        cin >> n[i];
        for (int j = 1, x; j <= n[i]; j++)
        {
            cin >> x;
            cnt[x]++;
        }
    }
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> Lv[i] >> p[i];
        for (int j = 1; j <= p[i]; j++)
            cin >> w[i][j];
    }
}

inline int DP()
{
    memset(dp, 0x80, sizeof dp), dp[0][0] = 0;
    int ans = 0, sum = 0, tot = 0;
    for (int L = 4; L >= 1; L--)
    {
        sum += cnt[L];
        for (int i = 1; i <= m; i++)
            if (Lv[i] == L)
            {
                tot++;
                for (int k = 0; k <= sum; k++)
                    dp[tot][k] = dp[tot - 1][k];
                for (int j = 1; j <= p[i]; j++)
                    for (int k = j; k <= sum; k++)
                        dp[tot][k] = max(dp[tot][k], dp[tot - 1][k - j] + w[i][j]);
            }
    }
    for (int i = 0; i <= sum; i++)
        ans = max(ans, dp[tot][i]);
    return ans;
}

signed main()
{
    Read();
    cout << DP();
}

```