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 可以从 2 和 3 推导得到。更简单点， 1 可以从最大合法值 3 推导得到， 2 也可以从最大合法值 3 推导得到 。

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

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