蓝桥杯2020省赛真题J 怪物猎人 装饰珠 问题（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();
}

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

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)'''得到总价值'''