【CF1201】D. Treasure Hunting(dp动态规划)

2023-10-30 03:48

本文主要是介绍【CF1201】D. Treasure Hunting(dp动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:https://codeforces.com/problemset/problem/1201/D

分析

可以发现,若一行中所有的宝箱刚好都被拿完之后,只可能停在最左边或者最右边的宝箱。
那么该行的最左边的宝箱点可以从上一行的最左边或最右边的宝箱点的状态转移过来。
我们设 d p [ i ] [ 0 ] dp[i][0] dp[i][0]为刚好拿完前 i i i行宝箱后停留在第 i i i最左端的宝箱的状态的最少步数, d p [ i ] [ 1 ] dp[i][1] dp[i][1]则为刚好拿完前 i i i行宝箱后停留在第 i i i最右端的宝箱的状态的最少步数。
转移方程即为:
d p [ i ] [ 0 ] = m i n ( d p [ i − 1 ] [ 0 ] + d i s ( l [ i − 1 ] , r [ i ] ) , d p [ i − 1 ] [ 1 ] + d i s ( r [ i − 1 ] , r [ i ] ) ) + r [ i ] − l [ i ] ; dp[i][0] = min(dp[i - 1][0] + dis(l[i - 1], r[i]), dp[i - 1][1] + dis(r[i - 1], r[i])) + r[i] - l[i]; dp[i][0]=min(dp[i1][0]+dis(l[i1],r[i]),dp[i1][1]+dis(r[i1],r[i]))+r[i]l[i];
d p [ i ] [ 1 ] = m i n ( d p [ i − 1 ] [ 0 ] + d i s ( l [ i − 1 ] , l [ i ] ) , d p [ i − 1 ] [ 1 ] + d i s ( r [ i − 1 ] , l [ i ] ) ) + r [ i ] − l [ i ] ; dp[i][1] = min(dp[i - 1][0] + dis(l[i - 1], l[i]), dp[i - 1][1] + dis(r[i - 1], l[i])) + r[i] - l[i]; dp[i][1]=min(dp[i1][0]+dis(l[i1],l[i]),dp[i1][1]+dis(r[i1],l[i]))+r[i]l[i];
要知道从某行x位置到下一行y位置的步数,就从距离x位置两边最近的安全列上去取个小即可。
具体看代码

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define fi first
#define se second
#define lson (k << 1)
#define rson (k << 1 | 1)const ll LINF = 1e18;
const int INF = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const ll P = 998244353;
const double eps = 1e-7;int n, m, k, q;
int l[N], r[N], sf[N];
ll dp[N][2];
vector<int> row;int dis(int x, int y)
{int res = INF;int qr = upper_bound(sf + 1, sf + 1 + q, x) - sf;int ql = qr - 1;if(ql > 0) res = min(res, abs(x - sf[ql]) + abs(y - sf[ql]));if(qr <= q) res = min(res, abs(x - sf[qr]) + abs(y - sf[qr]));return res;
}int main()
{ll ans = 0;scanf("%d%d%d%d",&n,&m,&k,&q);while(k--){int x, y;scanf("%d%d",&x,&y);if(l[x] == 0) l[x] = r[x] = y;else l[x] = min(l[x], y), r[x] = max(r[x], y);}for(int i=1;i<=q;i++) scanf("%d",&sf[i]);sort(sf + 1, sf + 1 + q);for(int i=1;i<=n;i++) if(l[i]) row.push_back(i);ans += row.back() - 1;if(row[0] == 1){dp[0][0] = r[row[0]] - 1 + r[row[0]] - l[row[0]];dp[0][1] = r[row[0]] - 1;}else{dp[0][0] = r[row[0]] - l[row[0]] + dis(1, r[row[0]]);dp[0][1] = r[row[0]] - l[row[0]] + dis(1, l[row[0]]);}for(int i=1;i<row.size();i++){dp[i][0] = min(dp[i - 1][0] + dis(l[row[i - 1]], r[row[i]]), dp[i - 1][1] + dis(r[row[i - 1]], r[row[i]])) + r[row[i]] - l[row[i]];dp[i][1] = min(dp[i - 1][0] + dis(l[row[i - 1]], l[row[i]]), dp[i - 1][1] + dis(r[row[i - 1]], l[row[i]])) + r[row[i]] - l[row[i]];}ans += min(dp[row.size() - 1][0], dp[row.size() - 1][1]);printf("%lld\n",ans);return 0;
}

这篇关于【CF1201】D. Treasure Hunting(dp动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,