BZOJ 1499 [NOI2005]瑰丽华尔兹 动态规划(+单调队列)

2024-03-30 16:48

本文主要是介绍BZOJ 1499 [NOI2005]瑰丽华尔兹 动态规划(+单调队列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

你跳过华尔兹吗?当音乐响起,当你随着旋律滑动舞步,是不是有一种漫步仙境的惬意?众所周知,跳华尔兹时,最重要的是有好的音乐。但是很少有几个人知道,世界上最伟大的钢琴家一生都漂泊在大海上,他的名字叫丹尼•布德曼•T.D.•柠檬•1900,朋友们都叫他1900。 1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上,很不幸他刚出生就被抛弃了,成了孤儿。1900孤独的成长在弗吉尼亚号上,从未离开过这个摇晃的世界。也许是对他命运的补偿,上帝派可爱的小天使艾米丽照顾他。可能是天使的点化,1900拥有不可思议的钢琴天赋:从未有人教,从没看过乐谱,但他却能凭着自己的感觉弹出最沁人心脾的旋律。当1900的音乐获得邮轮上所有人的欢迎时,他才8岁,而此时的他已经乘着海轮往返欧美大陆50余次了。虽说是钢琴奇才,但1900还是个孩子,他有着和一般男孩一样的好奇和调皮,只不过更多一层浪漫的色彩罢了:这是一个风雨交加的夜晚,海风卷起层层巨浪拍打着弗吉尼亚号,邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手马克斯•托尼晕船了,1900招呼托尼和他一起坐上舞厅里的钢琴,然后松开了固定钢琴的闸,于是,钢琴随着海轮的倾斜滑动起来。准确的说,我们的主角1900、钢琴、邮轮随着1900的旋律一起跳起了华尔兹,随着“嘣嚓嚓”的节奏,托尼的晕船症也奇迹般的消失了。后来托尼在回忆录上写道:大海摇晃着我们使我们转来转去快速的掠过灯和家具我意识到我们正在和大海一起跳舞真是完美而疯狂的舞者晚上在金色的地板上快乐的跳着华尔兹是不是很惬意呢?也许,我们忘记了一个人,那就是艾米丽,她可没闲着:她必须在适当的时候施展魔法帮助1900,不让钢琴碰上舞厅里的家具。不妨认为舞厅是一个N行M列的矩阵,矩阵中的某些方格上堆放了一些家具,其他的则是空地。钢琴可以在空地上滑动,但不能撞上家具或滑出舞厅,否则会损坏钢琴和家具,引来难缠的船长。每个时刻,钢琴都会随着船体倾斜的方向向相邻的方格滑动一格,相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法:如果不施魔法,则钢琴会滑动;如果施魔法,则钢琴会原地不动。艾米丽是个天使,她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行路程尽量长,这样1900会非常高兴,同时也有利于治疗托尼的晕船。但艾米丽还太小,不会算,所以希望你能帮助她。

Input

输入文件的第一行包含5个数N, M, x, y和K。N和M描述舞厅的大小,x和y为钢琴的初始位置(x行y列);我们对船体倾斜情况是按时间的区间来描述的,且从1开始计量时间,比如“在[1, 3]时间里向东倾斜,[4, 5]时间里向北倾斜”,因此这里的K表示区间的数目。以下N行,每行M个字符,描述舞厅里的家具。第i行第j列的字符若为‘ . ’,则表示该位置是空地;若为‘ x ’,则表示有家具。以下K行,顺序描述K个时间区间,格式为:si ti di。表示在时间区间[si, ti]内,船体都是向di方向倾斜的。di为1, 2, 3, 4中的一个,依次表示北、南、西、东(分别对应矩阵中的上、下、左、右)。输入保证区间是连续的,即 s1 = 1 si = ti-1 + 1 (1 < i ≤ K) tK = T

Output

输出文件仅有1行,包含一个整数,表示钢琴滑行的最长距离(即格子数)。

Sample Input

4 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3

Sample Output

6

HINT







传送门
没用单调队列竟然就过了……
起初的想法是dp[t][x][y]表示时间t,在(x,y)的最长距离,
那么dp[t][x][y]=max(dp[t-1][a][b],dp[t-1][x][y]),
(a,b)是(x,y)在t时间的方向的前一个位置的一格距离的那个位置(好绕= =)
显然O(Tnm)……是无法承受的。

观察到时间是一段一段的,考虑从时间段上做文章。
dp[t][x][y]表示在时间段t,在(x,y)的最长距离。
那么对于时间总长度为len的一个时间段,
中间用了一定次数的魔法,效果都是一样的,只用关心共走了几步;
比如从左走向右,dp[t][x][y]=max{dp[t-1][x][y-W]+W},W通过枚举得出。
那么时间复杂度O(N^3*K)……要爆炸。。

but!竟然A了= =
主要是正解虽然能推,但是我却不怎么会写……
= =2333
单调队列代码写得比较好的这篇吧:
orzdalao


……没有单调队列优化的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,sx,sy,K;
int s[N],t[N],d[N];
int dp[2][N][N];
bool a[N][N];
void DP(){memset(dp,128,sizeof(dp));dp[0][sx][sy]=0;for (int T=1;T<=K;T++)for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){if (a[i][j]) continue;int now=T&1,pre=now^1,tmp=t[T]-s[T]+1;if (d[T]==1){tmp=min(n-i,tmp);for (int k=0;k<=tmp;k++)if (a[i+k][j]) break;else dp[now][i][j]=max(dp[now][i][j],dp[pre][i+k][j]+k);}if (d[T]==2){tmp=min(i,tmp);for (int k=0;k<=tmp;k++)if (a[i-k][j]) break;else dp[now][i][j]=max(dp[now][i][j],dp[pre][i-k][j]+k);}if (d[T]==3){tmp=min(m-j,tmp);for (int k=0;k<=tmp;k++)if (a[i][j+k]) break;else dp[now][i][j]=max(dp[now][i][j],dp[pre][i][j+k]+k);}if (d[T]==4){tmp=min(j,tmp);for (int k=0;k<=tmp;k++)if (a[i][j-k]) break;else dp[now][i][j]=max(dp[now][i][j],dp[pre][i][j-k]+k);}}
}
int main(){scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&K);char tmps[N];for (int i=1;i<=n;i++){scanf("%s",tmps);for (int j=0;j<m;j++)if (tmps[j]=='x') a[i][j+1]=1;}for (int i=1;i<=K;i++) scanf("%d%d%d",&s[i],&t[i],&d[i]);DP();int ans=0;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)ans=max(ans,dp[K&1][i][j]);printf("%d\n",ans);return 0;
}



这篇关于BZOJ 1499 [NOI2005]瑰丽华尔兹 动态规划(+单调队列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

Java中常见队列举例详解(非线程安全)

《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,:本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一.队列定义 二.常见接口 三.常见实现类3.1 ArrayDeque3.1.1 实现原理3.1.2

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

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

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

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》:本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A

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

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

golang实现延迟队列(delay queue)的两种实现

《golang实现延迟队列(delayqueue)的两种实现》本文主要介绍了golang实现延迟队列(delayqueue)的两种实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录1 延迟队列:邮件提醒、订单自动取消2 实现2.1 simplChina编程e简单版:go自带的time

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

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

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

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