Codeforces Round 522 Div2 C. Playing Piano

作者: | 更新日期:

一个简单的动态规划题

一、题意

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

题意:输入钢琴的曲谱,每个调可以使用一个手指头按一下,手指头编号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)


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

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越