当前位置: 首页 > news >正文

蓝桥杯第三周算法竞赛D题E题

发现更多计算机知识,欢迎访问Cr不是铬的个人网站

D迷宫逃脱

file 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢?

这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候,会消耗一把钥匙。当没有钥匙的时候就不能移动了。想到这里,我们可以定义一个三维的dp数组.

  • 定义dp

dp[i][j][k]表示从位置(1,1)到(i,j)消耗k把钥匙的最大值

  • 初始化

memset(dp,-0x3f3f,sizeof(dp))

dp[i][j][0] = a[1][1]

  • 状态转移方程

dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k] + a[i][j])

dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k-1] + a[i][j])互质

dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k] + a[i][j])

dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1] + a[i][j])互质

  • 输出答案

从dp[n][m][0] ~ dp[n][m][k]找到最大的即可

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int main()
{//不加不能AC//优化输入/输出操作的性能,并精确控制输出的格式ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int n,m,p;//读入行宽与高还要钥匙数目cin>>n>>m>>p;//适当开大一点//dp[i][j][k]表示从(1,1)到(i,j)消耗k把钥匙的最大路径和LL dp[n+5][m+5][p+5];LL a[n+5][m+5];for(int i = 1; i <= n;i++)for(int j = 1; j <= m;j++)cin>>a[i][j];//初始化memset(dp,-0x3f3f,sizeof(dp));dp[1][1][0] = a[1][1];for(int i = 1;  i<= n; i++)for(int j = 1; j <= m;j++)for(int k = 0; k <= p; k++){//能够从上转移if(i > 1){if(gcd(a[i-1][j],a[i][j]) == 1) {if (k > 0)//不可能出现互质且没消耗一把钥匙的情况{ dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + a[i][j]); }}else { dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + a[i][j]); }}//能够从左边转移if(j > 1){if(gcd(a[i][j-1],a[i][j]) == 1) {if (k > 0)//不可能出现互质且没消耗一把钥匙的情况{ dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + a[i][j]); }}else { dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + a[i][j]); }}}//适当小一点LL maxx = -1e18;for(int i = 0; i <= p; i++)maxx = max(maxx,dp[n][m][i]);if(maxx>0)cout<<maxx<<endl;elsecout<<-1<<endl;return 0;
}

E深秋的苹果

file 这个是一道二分的题目,中规中矩写就行,但是注意此题右端点要开很大!

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=2e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n,m;
int a[N];
bool check (LL mid)
{LL pre = 0, sum = 0,group = 1;//刚开始就是一组for(int i = 0;  i < n;i++){if(pre + sum * a[i] <= mid)//可以分在一组{pre += sum*a[i];sum += a[i];}else//新开一组{group++;pre = 0;sum = a[i];//这组开始就是a[i]}if(group > m)return false;}return true;
}
int main() {//优化输入/输出操作的性能,并精确控制输出的格式ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);cin>>n>>m;for(int i = 0; i < n;i++)cin>>a[i];//二分思路LL l = 0, r = 3e18;//开大点,防止意外while( l < r){LL mid = l + (r - l)/ 2; //避免可能的超界if(check(mid)) { r = mid; }else { l = mid + 1; }}cout<<l<<endl;return 0;
}

本文由博客一文多发平台 OpenWrite 发布!

相关文章:

蓝桥杯第三周算法竞赛D题E题

发现更多计算机知识&#xff0c;欢迎访问Cr不是铬的个人网站 D迷宫逃脱 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢? 这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候&#xff0c;会消耗一把钥匙。当没有钥匙的时候就不能移动了。想…...

国家大基金三期线上金融正式倒计时!11月17日,共启芯片产业新篇章

国家大基金三期线上金融正式倒计时&#xff01;11月17日&#xff0c;共启芯片产业新篇章 新时代浪潮下&#xff0c;全球化进程不断推动各科技大国的核心发展&#xff0c;芯片作为强有力的竞争标志&#xff0c;是国与国之间的重要技术战争焦点。同时&#xff0c;国内基金发展势…...

Chrony让内网设备时间同步

Centos 搭建NTP服务器 背景&#xff1a;公司服务器时间不同步导致一些认证功能无法使用&#xff0c;网络设备时间不同步日志信息不准确&#xff0c;因此想要在内网搭建一个NTP服务器&#xff0c;作为客户端同步网络时间服务器&#xff0c;作为服务端为内网其他终端提供授时服务…...

在docker中部署MySQL

目录 1、拉取最新的镜像 2、创建mysql容器实例 3、启动mysql实例 4、进入mysql 交互环境 5、登录MySQL数据库 6、尽情享用mysql 1、拉取最新的镜像 docker image pull mysql 2、创建mysql容器实例 第一次执行&#xff0c;需要先创建容器并启动&#xff08;容器名是mys…...

百家网约车平台发布“阳光五条” 多举措加强司机保障

11月17日&#xff0c;免佣联盟百家网约车平台发布“阳光五条”&#xff0c;通过加大免佣力度、实行车费保镖司机版、72小时保护期等措施&#xff0c;加强对网约车司机的权益保障。 近年&#xff0c;交通运输部推动交通运输新业态平台企业落实“阳光行动”等工作&#xff0c;加…...

JXLS 导出多sheet,带页眉页脚

/*** 生成多sheet Excel* 带自定义页眉页脚** param templatePath* param sheetList* return* throws IOException*/public static byte[] generateMultiSheet(String templatePath, List<JxlsHelper2.SheetContext> sheetList) throws IOException {ByteArrayOutputStre…...

docker数据卷详细讲解及数据卷常用命令

docker数据卷详细讲解及数据卷常用命令 Docker 数据卷是一种将宿主机的目录或文件直接映射到容器中的特殊目录&#xff0c;用于实现数据的持久化和共享。Docker 数据卷有以下特点&#xff1a; 数据卷可以在一个或多个容器之间共享和重用&#xff0c;不受容器的生命周期影响。…...

智能井盖传感器能不能监测井盖位移

智能井盖传感器能够精准监测井盖的位移。这些传感器运用了前沿科技对井盖状态进行实时监测。一旦井盖出现异常移动传感器会立即捕捉到信号&#xff0c;并通过与互联网相连接的智能系统发出警报或记录数据。这种智能监测仪为城市或相关部门的井盖管理提供了实时数据支持&#xf…...

.bashrc文件中环境变量配置错误,导致linux命令无法正常使用

问题描述 配置环境变量时出错&#xff0c;导致linux命令无法使用 解决方案&#xff1a; 执行下面命令 export PATH/bin:/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin vim就可以使用了&#xff0c;将错误纠正 vim ~/.bashrc 环境生效 source ~/.bashrc…...

HTML易忽略的角落【目录】

目前已有文章 **** 篇 本专栏是汇集了一些HTML常常被遗忘的知识&#xff0c;这里算是温故而知新&#xff0c;往往这些零碎的知识点&#xff0c;在你开发中能起到炸惊效果。我们每个人都没有过目不忘&#xff0c;过久不忘的本事&#xff0c;就让这一点点知识慢慢渗透你的脑海。 …...

mysql8.0递归

sql举例&#xff1a; WITH recursive c1 AS( select * from course_category where id 1-1union allselect t2.* from course_category t2 INNER JOIN c1 where t2.parentidc1.id) select * from c1 ORDER BY orderby; 解释&#xff1a; WITH recursive c1 AS( //相当于创…...

处理机器学习数据集中字符串列(pandas.get_dummies)

如图&#xff0c;在数据集中week列的数据不是数值型&#xff0c;会导致我们在训练过程中难以处理。 而pandas库中有一个非常好用的函数&#xff0c;独热编码pandas.get_dummies(df) 使用此函数之后&#xff0c;会在原数据中新建各列代表Fri-Sun&#xff0c;值为0或1&#xff…...

一个UE无法注册的问题

问题场景是环境中只有一个小区&#xff0c;UE在找到这个小区&#xff0c;收到MIB SIB1后一直不发起注册。我想这大概是和S准则不满足有关系了&#xff0c;这个问题基本是又没啥好看的了&#xff0c;太简单了&#xff0c;在SIB1周围找找就解决了&#xff0c;于是我发现了以下log…...

自媒体剪辑必备,6个音效素材网站,你值得拥有。

这6个剪辑必备的音效素材网站一定要收藏好了&#xff0c;有了这几个网站能让你在剪辑的时候事半功倍&#xff0c;还不用担心版权问题。话不多说&#xff0c;直接上干货。 1、菜鸟图库 https://www.sucai999.com/audio.html?vNTYwNDUx 菜鸟图库是一个综合性素材网站&#xff…...

uniapp Android如何授权打开系统蓝牙Bluetooth?

uniapp Android如何授权打开系统蓝牙&#xff1f; 使用uniapp开发蓝牙项目过程中&#xff0c;涉及到检测手机系统蓝牙是否打开功能&#xff0c;这里介绍Android&#xff0c;iOS暂时没有找到优方法。朋友们如果有好的方案&#xff0c;欢迎评论分享~ 文章目录 uniapp Android如何…...

图论与网络优化2

CSDN 有字数限制&#xff0c;因此笔记分别发布&#xff0c;目前&#xff1a; 【笔记1】概念与计算、树及其算法【笔记2】容量网络模型 4 最大流及其算法 4.1 容量网络模型 4.1.1 容量网络 容量网络&#xff1a;如果一个加权有向网络 D D D 满足如下三个条件&#xff1a;①…...

ES Kibana windows 安装

ES & Kibana windows 安装 声明&#xff1a; 本文没有实际操作过&#xff0c;只记录。具体操作请参考 ES & Kibana 安装 该文章 JDK1.8&#xff0c;最低要求&#xff01;ElasticSearch客户端&#xff0c;界面工具&#xff01; Java开发&#xff0c;ElasticSearch的版…...

分布式事务seata的使用

分布式事务介绍 在微服务架构中&#xff0c;完成某一个业务功能可能需要横跨多个服务&#xff0c;操作多个数据库。这就涉及到到了分布式事务&#xff0c;需要操作的资源位于多个资源服务器上&#xff0c;而应用需要保证对于多个资源服务器的数据操作&#xff0c;要么全部成功&…...

使用宝塔面板安装mysql

1.第一步 在官网https://www.bt.cn/new/download.html下载页面直接在服务器控制面板复制这里的代码下载即可 2.第二步 下载好后按照服务器面版上有个公网地址&#xff0c;含有用户名和密码&#xff0c;保存好&#xff0c;然后通过公网地址打开一个网页&#xff0c;绑定自己注册…...

Flink 支持三种时间语义

在 Apache Flink 中&#xff0c;时间在流处理中是一个重要的概念&#xff0c;而时间语义则用于定义事件发生的时间。Flink 支持三种时间语义&#xff0c;分别是&#xff1a; Processing Time&#xff08;处理时间&#xff09;&#xff1a; 以机器的系统时间为基准&#xff0c;…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...