Codeforces Round 522 Div2 C. Playing Piano

栏目: 编程工具 · 发布时间: 6年前

内容简介:地址: http://codeforces.com/contest/1079/problem/C题意:输入钢琴的曲谱,每个调可以使用一个手指头按一下,手指头编号1到5。

一、题意

地址: http://codeforces.com/contest/1079/problem/C

Codeforces Round 522 Div2 C. Playing Piano

题意:输入钢琴的曲谱,每个调可以使用一个手指头按一下,手指头编号1到5。

要求1:相邻的两个调,调更高时,需要使用编号更高的指头。

要求2:相邻的两个调,相等时,两个指头需要不同。 求输出一直弹奏的指法。

二、分析

由于每个位置顶多有5个指法,我们可以计算出每个位置的5个指法是否可行。

从左右到看,一个位置的某个指法是否可行,可以由上个位置推导出来。

所以这是典型的动态规划题,而且是初级 DP 题。

展开来看,依旧是从左到右。

第一个位置任何一个手指都可以按。

第二个位置需要根据第一个调的值以及指法来计算。

具体计算方法是第二个位置的某个指法,我们循环上个位置的所有指法,判断上个位置指法是否合法,以及能否满足题目的两个要求。满足了当前指法就是合法的。

由于题意要求输出其中一个路径,合法的时候我们可以保存这个合法指法是从哪个指法推导过来的。

这样从左到右就可以计算出最后一个位置的所有合法指法。

如果最后一个位置存在合法指法,逆向推导即可计算出合法路径。

默认情况下,复杂度是 O(n * 5 * 5)

在从左到有推导的时候,我们可以得出这样一个结论: 如果b是大于上个位置的合法指法,那么大于b的都是合法的。 因为最大的指法大于b,所以最大的指法肯定也是合法的。

因此,我们可以根据最大的指法快速判断当前指法是不是合法的。

例如,对于第 2 个位置 ,合法指法是 1,2,3

第 3 个位置小于第 2 个位置,我们可以快速得到第3个位置的 1 是合法指法。

因为 1 可以从 23 推导得到。更简单点, 1 可以从最大合法值 3 推导得到, 2 也可以从最大合法值 3 推导得到 。

由此,我们可以维护一个上个位置的最大合法值和最小合法值(单点最值,不是区间),从而少一次循环,复杂度降为 O(n * 5)

Codeforces Round 522 Div2 C. Playing Piano

本文首发于公众号:天空的代码世界,微信号:tiankonguse-code。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

30天自制操作系统

30天自制操作系统

[日] 川合秀实 / 周自恒、李黎明、曾祥江、张文旭 / 人民邮电出版社 / 2012-8 / 99.00元

自己编写一个操作系统,是许多程序员的梦想。也许有人曾经挑战过,但因为太难而放弃了。其实你错了,你的失败并不是因为编写操作系统太难,而是因为没有人告诉你那其实是一件很简单的事。那么,你想不想再挑战一次呢? 这是一本兼具趣味性、实用性与学习性的书籍。作者从计算机的构造、汇编语言、C语言开始解说,让你在实践中掌握算法。在这本书的指导下,从零编写所有代码,30天后就可以制作出一个具有窗口系统的32位......一起来看看 《30天自制操作系统》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

在线进制转换器
在线进制转换器

各进制数互转换器

随机密码生成器
随机密码生成器

多种字符组合密码