题目内容

你得到了$n$块「记忆碎片」，它们排成一排，第$i$块碎片所对应记忆发生的时间为$t_i$;。t1,t2,...,tn是1到n的一个排列。

你希望重新排列这$n$块碎片，使它们单调递增(即重排为$1,2,...,n$) ，排列的规则为:

• 你有一个能力值$k$，每次你可以选择两块发生时间相差不超过$k$的碎片，交换它们的顺序;
• 由于发生时间过于靠近的两块碎片很难回想，对于两块发生时间相差恰好为$1$的碎片，交换它们需要消耗你$1$点精力;

题解

题面描述

我们有$n$块「记忆碎片」，它们按顺序排列，每块对应的记忆发生时间为$t_i$，且$t_1,t_2,\dots,t_n$构成$1$到$n$的一个排列。目标是将这些碎片重新排列成单调递增的顺序，也就是排序为$1,2,\dots,n$。允许的交换操作必须满足：

• 每次只能交换两块**发生时间相差不超过$k$**的碎片；
• 如果交换的两块碎片的记忆时间差恰好为$1$，则需要消耗$1$点精力（即代价$1$）；
• 如果交换碎片的记忆时间差大于$1$（但不超过$k$），则交换是免费的。

要求计算出在最优策略下恢复记忆所需消耗的最少精力。