有一把锁从左到右有n个数，组成了一个序列。只要将锁设置为输入任意单峰序列即可打开。具体为：a_1 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n\quad (1 \le i \le n)a 1 ≤⋯≤a i ≥a i+1≥⋯≥a n(1≤i≤n)。锁是拨动式的即拨一下就能换成临近的一个数（0和9可以互换求最少拨几下可以开锁。 代码

以下是使用 Python 3 实现的动态规划算法：

def solve(n, a):
    INF = 10**9
    dp = [[INF] * (n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        dp[1][i] = i-1
    for i in range(2, n+1):
        for j in range(2, i+1):
            for k in range(1, j):
                dp[i][j] = min(dp[i][j], dp[j-1][k]+i-j+1+max(0, max(a[j:i])-a[j-1]))
    return min(dp[n][j] for j in range(1, n+1))

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

其中，`dp[i][j]` 表示将前 $i$ 个数变成单峰序列，其中峰值是第 $j$ 个数，需要拨动的最少次数。初始化时，将 `dp[1][i]` 赋值为 $i-1$，表示将前 $1$ 个数变成单峰序列，峰值在位置 $i$，需要拨动的最少次数。

接下来，按照上述状态转移方程，从前往后依次计算每个状态的值。最终答案为 $\min\{dp[n][j]\}$，其中 $j\in[1,n]$。

时间复杂度为 $O(n^3)$，可以通过此题。

相关问题

这把锁从左到右有 � n 个数，组成了一个序列 { � } {a}。 由于 GOD_hj 的记性不好，所以只要将锁设置为输入任意单峰序列即可打开。具体为： � 1 ≤ ⋯ ≤ � � ≥ � � + 1 ≥ ⋯ ≥ � � ( 1 ≤ � ≤ � ) a 1 ​ ≤⋯≤a i ​ ≥a i+1 ​ ≥⋯≥a n ​ (1≤i≤n) GOD_hj 的锁是拨动式的，即拨一下就能换成临近的一个数（ 0 0 和 9 9 可以互换）。 求最少拨几下可以开锁。

这是一个经典的信封嵌套问题，也可以称为最长不降子序列问题。可以使用动态规划求解，时间复杂度为 O(n^2) 或 O(nlogn)。以下是 O(nlogn) 的解法：

定义一个数组 d，d[i] 表示长度为 i 的最长不降子序列的末尾元素的最小值。初始化 d[1] = a[1]，其余为正无穷大。

遍历整个序列，对于每个元素 a[i]，在数组 d 中二分查找第一个大于等于 a[i] 的位置，更新 d[j] = a[i]，其中 j 为查找到的位置。如果查找到的位置 j 大于当前最长的不降子序列长度 len，则更新 len = j。

最终最长不降子序列的长度为 len，需要拨动的次数为 n - len。

代码如下：

GOD_hj 有一把数字密码锁，但是他陷于 whk，没时间来开锁。这把锁从左到右有 nn 个数，组成了一个序列 \{a\}{a}。 由于 GOD_hj 的记性不好，所以只要将锁设置为输入任意单峰序列即可打开。具体为： a_1 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n\quad (1 \le i \le n) a 1 ​ ≤⋯≤a i ​ ≥a i+1 ​ ≥⋯≥a n ​ (1≤i≤n) GOD_hj 的锁是拨动

的，每次只能将一个数字上下拨动一格。现在问你：最少需要多少次拨动才能将锁打开？

注：单峰序列是指序列从左到右单调不降，从左到右单调不增的序列。

我的回答是：

先找到最大值的下标 $i$，然后分别从开头到 $i$ 和从结尾到 $i$ 找到单调不降的长度 $len1$ 和 $len2$，最终答案为 $n-\max(len1,len2)$。

时间复杂度 $O(n)$。

代码实现：

n = int(input())
a = list(map(int, input().split()))

i = a.index(max(a))
len1, len2 = 1, 1
for j in range(i-1, -1, -1):
    if a[j] <= a[j+1]:
        len1 += 1
    else:
        break
for j in range(i+1, n):
    if a[j] <= a[j-1]:
        len2 += 1
    else:
        break

print(n - max(len1, len2))