蓝桥杯官网试题 PREV-61 历届真题装饰珠【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法

红目香薰

发布于 2022-11-30 17:08:37

2480

发布于 2022-11-30 17:08:37

文章被收录于专栏：CSDNToQQCode

为帮助大家能在6月18日的比赛中有一个更好的成绩，我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。

今年的最大目标就是能为【一亿技术人】创造更高的价值。

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

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

已知猎人身上一共有 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≤Pj≤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

Data

样例输出

Data

样例说明

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

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

None

4 颗技能 1 装饰珠，4 颗技能 2 装饰珠 W1(4)+W2(4)=5+15=20。

评测用例规模与约定

对于 30 的评测用例，1≤Ni≤10, 1≤M≤20, 1≤Wj(k)≤500；

对于所有评测用例，1≤Ni≤50, 1≤M≤10000, 1≤Wj(k)≤10000。

C++

#include<cstdio>
#include<algorithm>
int read(){
    int n=0;char c=getchar();bool f=0;
    while(c!='-'&&(c<'0'||c>'9'))c=getchar();
    if(c=='-'){f=1;c=getchar();}
    while(c>='0'&&c<='9'){n=n*10+c-'0';c=getchar();}
    if(f)return -n;
    return n;
}
int cnt[6];
int m;
struct diamond{
    int l,p;int w[9];
};
diamond ls[10007];
bool operator<(diamond a,diamond b){
    return a.l>b.l;
}
long long ans[600];
int main(){
    for(int i=1;i<=6;i++){
        int n=read();
        for(int j=1;j<=n;j++){
            int l=read();
            cnt[l]++;
        }
    }
    for(int i=3;i>=1;i--)cnt[i]+=cnt[i+1];
    m=read();
    for(int i=1;i<=m;i++){
        ls[i].l=read();ls[i].p=read();
        for(int j=1;j<=ls[i].p;j++){
            ls[i].w[j]=read();
        }
    }
    std::sort(ls+1,ls+m+1);
    for(int i=1;i<=m;i++){
        for(int k=cnt[ls[i].l];k>=0;k--){
            for(int j=1;j<=ls[i].p;j++){
                if(k-j<0)continue;
                long long cur=ans[k-j]+ls[i].w[j];
                if(ans[k]<cur)ans[k]=cur;
            }
        }
    }
    long long res=0;
    for(int i=0;i<=cnt[1];i++){
        if(ans[i]>res)res=ans[i];
    }
    printf("%lld\n",res);
}

C

#include<stdio.h>
#include<string.h>
int n[305],cnt[5]={0},lv[10010],p[10010],w[10010][10];//lv[i]ÖéµÈ¼¶£¬p[i]ÖéÊýÁ¿ÉÏÏÞ 
int dp[10010][305];
int max(int x,int y){
	return x>y?x:y;
}
int main(){
	int ans=0,tot=0,sum=0;//tot¿ÉÓÃÖé,sum¿ÉÓÃ¿×
	int n,m,i,j,x,k,L;
	memset(dp,0,sizeof(dp));
	for(i=1;i<=6;i++){
		scanf("%d",&n);
		for(j=1;j<=n;j++) scanf("%d",&x),cnt[x]++;
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		scanf("%d%d",&lv[i],&p[i]);
		for(j=1;j<=p[i];j++) scanf("%d",&w[i][j]);
	}
	for(L=4;L>=1;L--){
		sum+=cnt[L];
		for(i=1;i<=m;i++)
			if(lv[i]==L){
				tot++;
				for(k=0;k<=sum;k++) dp[tot][k]=dp[tot-1][k];
				for(j=1;j<=p[i];j++)//tot¸öÖéÕ¼k¸ö¿× 
					for(k=j;k<=sum;k++)
						dp[tot][k]=max(dp[tot][k],dp[tot-1][k-j]+w[i][j]);
			}
	}
	for(i=0;i<=sum;i++) ans=max(ans,dp[m][i]);
	printf("%d\n",ans);
	return 0;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException  {
		Reader.init(System.in);
		int[][] equip = new int[6][50];
		ArrayList<int[]> W = new ArrayList<>();
		int skillNum = 0;
		
		for(int i=0;i<6;i++) {
			equip[i][0] = Reader.nextInt();
			for(int j=0;j<equip[i][0];j++) {
				equip[i][j+1] = Reader.nextInt();
			}
		}
		
		skillNum = Reader.nextInt();

		for(int i=0;i<skillNum;i++) {
			int[] ball = new int[9];
			ball[0] = Reader.nextInt();
			ball[1] = Reader.nextInt();
			for(int j=0;j<ball[1];j++)
				ball[j+2] = Reader.nextInt(); 
			W.add(ball);
		}
		
		Comparator<int[]> comparator = new Comparator<int[]>() {
		 @Override 
		 	 public int compare(int[] o1,int[] o2) { 
			 return o1[0] - o2[0]; 
			 } 
		 };
		Collections.sort(W,comparator);
		int w = 0;
		int[][] v = new int[skillNum][9];
		for(int i=0;i<6;i++)
			w += equip[i][0];
		//q是孔的等级
		int[] q = new int[w];
		int tool = 0;
		for(int i=0;i<6;i++)
			for(int j=0;j<equip[i][0];j++)
				q[tool++] = equip[i][j+1];
		Arrays.sort(q);
		
		//v是珠的等级和w（i）
		for(int i=0;i<skillNum;i++)
			for(int j=0;j<=W.get(i)[1]+1;j++)
				if(j == 0) v[i][j] = W.get(i)[0];
				else if(j == 1) v[i][j] = 0;
				else v[i][j] = W.get(i)[j];
		//dp
		int[][] dp = new int[skillNum+1][w+1];
		for(int i=0;i<skillNum+1;i++)
			dp[i][0] = 0;
		for(int i=0;i<w+1;i++)
			dp[0][i] = 0;
		int[][] aa = new int[4][w];
		
		for(int j=0;j<4;j++) {
			int c = 0;
			for(int i=0;i<q.length;i++) {
				if(q[i]>=j+1) aa[j][i] = ++c; 
			}
		}
		//开始，以上操作都是将数据读取，这里开始进行背包
		//出错的原因在于没有把每一个状态都进行遍历，在任意位置插入任意多的另一种珠子
		for(int i=1;i<skillNum+1;i++) {
			int s = W.get(i-1)[1];
			for(int j=1;j<w+1;j++) {
					int count = 0;
					int bb = v[i-1][0];
					//装饰孔按顺序一个一个开放，装饰珠从低到高排序，每开发一个装饰孔就统计到目前开放的装饰孔中有几个能放的装饰孔count
					count = aa[bb-1][j-1];
					//g是从哪里开始插入
					
						//要插多少个
						for(int k=1;k<j+1;k++) {
							//s是装饰珠能产生价值的最大数量
							if(k>s || k>count) {
								dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
								break;
							}
							else {
								dp[i][j] = Math.max(dp[i-1][0] + v[i-1][1+k] - v[i-1][1] + dp[i-1][j-k] -dp[i-1][0], dp[i][j]);
								dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
							}
						}
					
				}
		}
		System.out.println(dp[skillNum][w]);
		
	}
}


class Reader{
	static BufferedReader reader;
	static StringTokenizer tokenizer;
	
	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(System.in));
		tokenizer = new StringTokenizer("");
	}
	
	static String next() throws IOException {
		while(tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
	
	static int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(next());
	}
}

Python

import os
import sys

vec1 = []
vec2 = []
vec3 = []
vec4 = []
vec = []
dp = [0] * 301
sum = [0] * 6

for i in range(1, 7):
    mp = list(map(int, input().split()))
    for i in range(1, len(mp)):
        sum[mp[i]] += 1
m = int(input())
for i in range(1, m + 1):
    mp = list(map(int, input().split()))
    b = []
    for j in range(2, len(mp)):
        x = mp[j]
        b.append(x)
    if mp[0] == 1:
       vec1.append(b)
    if mp[0] == 2:
        vec2.append(b)
    if mp[0] == 3:
        vec3.append(b)
    if mp[0] == 4:
        vec4.append(b)
V = 0
cnt = 0
for l in range(4, 0, -1):
    V += sum[l]
    if l == 1:
        vec = vec1
    elif l == 2:
        vec = vec2
    elif l == 3:
        vec = vec3
    elif l == 4:
        vec = vec4
    for i in vec:
        k = int(V)
        while k >= 0:
            for j in range(0, len(i)):
                if k - j - 1 >= 0:
                     if dp[k - j - 1] + i[j] > dp[k]:
                            dp[k] = dp[k - j - 1] + i[j]
                else:
                     break
            k -= 1
ans = 0
for h in range(0, V + 1):
    ans = max(ans, dp[h])

print(ans)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-31，如有侵权请联系 cloudcommunity@tencent.com 删除

uml

python

c++

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度