NOIP 提高 2011 第一轮 第 22 题：定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串

题目

定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串 $\texttt{BCA}$ 可以将 $\texttt A$ 移到 $\texttt B$ 之前，变字符串 $\texttt{ABC}$。如果要将字符串 $\texttt{DACHEBGIF}$ 变成 $\texttt{ABCDEFGHI}$ 最少需要次操作。

答案

4

题解

考点定位

本题考「最少移动排序」,对应大纲 2.1.5 组合分析（难度【4】）。

解题过程

DACHEBGIF → ABCDEFGHI。每次移动一个元素到任意位置。最优策略：保留最长「已相对有序」的子序列不动，移动其余。目标串中 D,A,C,H,E,B,G,I,F：保留 A,C,E,G,I（原串中按序出现的、应留在原位的元素）：DACH EBGIF 中 A、C、E、G、I 位置相对有序 ✓（其余 4 个 D,H,B,F 各移一次）。能否只移 3？需保留 6 个按序元素：A,C,E,G,I 只有 5 个加 H？A,C,E,H?,G,I——H 在 G 前 ✗。最长为 5 ⇒ 移动 9−5=4 次。

答案：4。

易错提醒

① 一次移动一个元素到任意位置 ⇒ 最少移动数 = n − 最长「保持原位」递增子序列；② 与 LIS 的区别：这里保留的元素连相对顺序都不变（本质是找最长「无需移动」子序列）。