Acwing 3306.装珠饰(十一届蓝桥java/py组J题)

2023-10-19 00:52

本文主要是介绍Acwing 3306.装珠饰(十一届蓝桥java/py组J题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 分析:

        6件装备作为一个整体去看待!!!加的效果是看总的装备数目

        分组背包的一个特点:每一个组里面只能取出一个物品,这里是把抽象成不同的方案数(有点多重背包的二进制处理方法的感觉。)

        

 

代码实现:

#include <iostream>
using namespace std;
const int N = 1e4 + 10;int cnt[5];             // 表示cnt_i对应的总的孔的数目
int capacity[5];        // 表示四个阶段的容量
int zhu_rank[N];        // 珠宝上的等级应该<=嵌入装饰孔的等级
int upper_bound[N];     // 每个珠宝装饰的一个上限
int w[N][10];
int f[N];               // f_ij表示只用前i个珠子,用<=孔容量j的情况下=====>得到的总价值
int n;  // n种装饰珠int main()
{// 装饰孔数量和等级的读取for(int i = 0; i < 6; i ++){int y; cin >> y;int rk;/*实际上,将6个武器作为一个整体,是不关心每个武器上的具体有多少相应等级的孔的,只关心6个武器中孔不同等级的总数.*/for(int j = 0; j < y; j ++)cin >> rk, cnt[rk] ++;}/*先是使用rank=4的孔,这时候孔的数量就是背包的容量;然后使用rank=3的孔,这时候背包的容量应该是rank=4的孔数量+rank=3的孔数量....*/for(int i = 1; i <= 4; i ++)            // 将每个阶段的背包容量预处理出来capacity[i] = capacity[i - 1] + cnt[4 - i + 1];cin >> n; // n种装饰珠,一个小细节:下标统一从1开始.for(int i = 1; i <= n; i ++){cin >> zhu_rank[i] >> upper_bound[i];for(int j = 1; j <= upper_bound[i]; j ++)cin >> w[i][j];}// 分组背包dpfor(int rk = 4; rk; rk --) // 孔的等级从高到低逐个释放,这样子就不用担出现L级的珠宝对于L-1级的孔不适用的非法背包状态了{for(int i = 1; i <= n; i ++)    // 一次考虑每一个珠宝if(zhu_rank[i] == rk)       // 不重不漏(主要是防止重复)for(int j = capacity[4 - rk + 1]; j >= 0; j --)for(int k = 0; k <= upper_bound[i]; k ++)if(j >= k)f[j] = max(f[j], f[j - k] + w[i][k]);   //选k方案}int res = -1; for(int i = 0; i <= capacity[4]; i ++)res = max(res, f[i]);cout << res << endl;return 0;
}

这篇关于Acwing 3306.装珠饰(十一届蓝桥java/py组J题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/236225

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis