藍橋杯2020省賽真題J 怪物獵人 裝飾珠 問題（C++解法）（java和Python附在后面）

【問題描述】
在怪物獵人這一款游戲中，玩家可以通過給裝備鑲嵌不同的裝飾珠來獲取 相應的技能，以提升自己的戰斗能力，
已知獵人身上一共有 6 件裝備，每件裝備可能有若干個裝飾孔，每個裝飾孔有各自的等級，可以鑲嵌一顆小于等于自身等級的裝飾珠 (也可以選擇不鑲嵌)，
裝飾珠有 M 種，編號 1 至 M，分別對應 M 種技能，第 i 種裝飾珠的等級為 Li，只能鑲嵌在等級大于等于 Li 的裝飾孔中，
對第 i 種技能來說，當裝備相應技能的裝飾珠數量達到 Ki 個時，會產生Wi(Ki) 的價值，鑲嵌同類技能的數量越多，產生的價值越大，即 Wi(Ki ? 1) < Wi(Ki)，但每個技能都有上限 Pi(1 ≤ Pi ≤ 7)，當裝備的珠子數量超過 Pi 時，只會產生 Wi(Pi) 的價值，
對于給定的裝備和裝飾珠資料，求解如何鑲嵌裝飾珠，使得 6 件裝備能得到的總價值達到最大，

【輸入格式】
輸入的第 1 至 6 行，包含 6 件裝備的描述，其中第 i 的第一個整數 Ni 表示第 i 件裝備的裝飾孔數量，后面緊接著 Ni 個整數，分別表示該裝備上每個裝飾孔的等級 L(1 ≤ L ≤ 4)，
第 7 行包含一個正整數 M，表示裝飾珠 (技能) 種類數量，
第 8 至 M + 7 行，每行描述一種裝飾珠 (技能) 的情況，每行的前兩個整數Lj(1 ≤ Lj ≤ 4) 和 Pj(1 ≤ Pi ≤ 7) 分別表示第 j 種裝飾珠的等級和上限，接下來Pj 個整數，其中第 k 個數表示裝備該中裝飾珠數量為 k 時的價值 Wj(k)，

【輸出格式】
輸出一行包含一個整數，表示能夠得到的最大價值，

【樣例輸入】

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

題解

C++代碼如下

#include <iostream>
#include <cstring>
#include <aLgorithm>
using namespace std;

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();
}

java代碼如下

import java.util.*;
public class Main {
public static void main(String[] args) {
    int []zhu,l= new int[]{0,0,0,0,0,0};
    int[][] zsk;
    Scanner sc=new Scanner(System.in);
    for(int i=0;i<6;i++) {
        int ko=sc.nextInt();
        for(int j=0;j<ko;j++) {
            int li=sc.nextInt();
            l[li+1]++;
        }
    }
    int M=sc.nextInt();
    int z=l[4]+l[5]+l[2]+l[3];
    l[3]=l[2]+l[3];
    l[4]=l[3]+l[4];
    zsk=new int[M+1][z+1];
    for(int i=0;i<z+1;i++)zsk[0][i]=0;
    for(int i=0;i<M+1;i++)zsk[i][0]=0;
    for(int i=1;i<M+1;i++) {
        int bt=i;
        int li=sc.nextInt();
        int lim=sc.nextInt();
        zhu=new int[lim];
        for(int j=0;j<lim;j++)zhu[j]=sc.nextInt();
        for(int i1=1;i1<l[li]+1;i1++)zsk[M][i1]=zsk[M-1][i1];
        for(int i1=l[li]+1;i1<z+1;i1++) {
            int max=0;
            for(int j=0;i1-j-1>=l[li]&&j<zhu.length;j++)
                max=Math.max(max, zhu[j]+zsk[i-1][i1-j-1]);
            max=Math.max(max, zsk[i-1][i1]);
            zsk[i][i1]=max;
        }
    }
    System.out.println(zsk[M][z]);
}
}

python解法如下

import os
import sys

s = [];r = [];m = []

for i in range(6):
    s.append(list(map(int,input().split())))
n = int(input())
for i in range(n):
    r.append(list(map(int,input().split())))
for i in range(6):
    p = s[i]
    for j in range(n):
        if i == 0:
            m.append(p[1:].count(int(j+1)))
        else:
            m[j] += p[1:].count(int(j+1))

'''print(m)''' '''用m[j]記錄6件裝備共有 j+1級孔m[j]個'''
mm = m'''假設j級孔全用j級珠子'''
up = [];down = [];'''up記錄加一顆珠子提升的價值，down記錄少一顆珠子減少的價值'''
def up1(k):
    if mm[k]>=r[k][1]:
        return 0
    elif mm[k] == 0:
        return r[k][2]
    else:
        return r[k][2+mm[k]]-r[k][1+mm[k]]
def down1(k):
    if mm[k] == 1:
        return r[k][2]
    elif mm[k]>r[k][1]:
        return 0
    else :
        return r[k][1+mm[k]]-r[k][mm[k]]
for i in range(n):
    up.append(up1(i))
    down.append(down1(i))

'''print(up,down)'''
'''第n+1級孔，如果1到n級孔中珠子加1的價值比它減少1顆的價值大，則數值各加1、減1，up、down更新'''
def main1(n):
    if n == 0:
        return
    while max(up[:n])>down[n] and mm[n]>0:
        t = up.index(max(up[:n]))
        mm[t] += 1
        up[t] = up1(t)
        mm[n] -= 1
        down[n] = down1(n)
    main1(n-1)
    return
point = 0
main1(n-1)'''輸入有n級，為了和形參統一，此處減1'''
'''print(up,down)
print(mm)'''
for i in range(n):
    if mm[i] != 0:
        point += r[i][1+mm[i]]
print(point)'''得到總價值'''