T1188密码锁 超难 2024 贪心 STEMA dp T6 1月 区间DP 标准IO 传统题 来源 TomAnderson 时间限制 1000ms 内存限制 256MB 提示信息： 密码锁：由 n 个从左到右并排的圆环组成，每个圆环上都有 10 个数字（0~9），蓝色框内为密码显示区，每个圆环在密码显示区只能显示一个数字，如图所示。可以拨动圆环，来改变密码显示区显示的数字。 当密码显示区的数字与密码一致时，密码锁就会被打开。 image 编程实现： 有一个由 n 个圆环组成的密码锁，和一个 n 位的密码 S（S 由 1~9 中的数字（包含 1 和 9）组成）。每次操作只能选择一个或位置连续的多个圆环拨动。当 S 中的字符从左到右依次显示在密码显示区时，密码锁会被打开。 已知每个圆环在密码显示区初始数字都为 0，请计算最少需要操作多少次，才能打开密码锁。 注意: 1、如果选择了其中一个圆环，可将该圆环中任意一个数字拨动到密码显示区，表示 1 次操作； 例如：将第 3 个圆环拨动到数字 4，表示 1 次操作： image 2、如果选择了位置连续的多个圆环，只能将这些圆环

以下是使用 Python 实现的代码： ```python # 读取输入 n = int(input()) S = input() # 创建一个三维的动态规划数组 dp # dp[i][j][k] 表示将区间 [i, j] 的圆环拨到数字 k 所需的最少操作次数 dp = [[[float('inf')] * 10 for _ in range(n)] for _ in range(n)] # 初始化 dp 数组 for i in range(n): for k in range(10): # 单个圆环拨到数字 k 的操作次数 dp[i][i][k] = abs(int(S[i]) - k) # 区间长度从 2 到 n 进行遍历 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 for k in range(10): # 先考虑将整个区间 [i, j] 拨到数字 k 的情况 dp[i][j][k] = min(dp[i][j - 1][k], dp[i + 1][j][k]) + abs(int(S[j]) - k) # 枚举分割点，将区间 [i, j] 分成 [i, m] 和 [m + 1, j] for m in range(i, j): dp[i][j][k] = min(dp[i][j][k], dp[i][m][k] + dp[m + 1][j][k]) # 找到将整个区间 [0, n - 1] 拨到任意数字所需的最少操作次数 ans = float('inf') for k in range(10): ans = min(ans, dp[0][n - 1][k]) # 输出结果 print(ans) ``` 代码解释： 1. 输入读取：首先读取圆环的数量 `n` 和密码字符串 `S`。 2. 动态规划数组初始化：创建一个三维数组 `dp`，其中 `dp[i][j][k]` 表示将区间 `[i, j]` 的圆环拨到数字 `k` 所需的最少操作次数。对于单个圆环，将其拨到数字 `k` 的操作次数为该圆环的目标数字与 `k` 的差值的绝对值。 3. 区间动态规划：通过枚举区间长度、区间起始位置和目标数字，计算将区间 `[i, j]` 拨到数字 `k` 的最少操作次数。枚举分割点，将区间 `[i, j]` 分成两个子区间，取最小操作次数。 4. 结果计算：在所有可能的目标数字中，找到将整个区间 `[0, n - 1]` 拨到该数字所需的最少操作次数。 5. 输出结果：输出最少操作次数。 复杂度分析： - 时间复杂度：$O(n^3 \times 10)$，其中 $n$ 是圆环的数量。 - 空间复杂度：$O(n^2 \times 10)$，主要用于存储动态规划数组。 [2025-11-08 22:09:01 | AI问答 | 718点数解答]