题目内容
你得到了n块「记忆碎片」,它们排成一排,第i块碎片所对应记忆发生的时间为ti;。t1,t2,...,tn是1到n的一个排列。
你希望重新排列这n块碎片,使它们单调递增(即重排为1,2,...,n) ,排列的规则为:
- 你有一个能力值k,每次你可以选择两块发生时间相差不超过k的碎片,交换它们的顺序;
- 由于发生时间过于靠近的两块碎片很难回想,对于两块发生时间相差恰好为1的碎片,交换它们需要消耗你1点精力;
题解
题面描述
我们有n块「记忆碎片」,它们按顺序排列,每块对应的记忆发生时间为ti,且t1,t2,…,tn构成1到n的一个排列。目标是将这些碎片重新排列成单调递增的顺序,也就是排序为1,2,…,n。允许的交换操作必须满足:
- 每次只能交换两块**发生时间相差不超过k**的碎片;
- 如果交换的两块碎片的记忆时间差恰好为1,则需要消耗1点精力(即代价1);
- 如果交换碎片的记忆时间差大于1(但不超过k),则交换是免费的。
要求计算出在最优策略下恢复记忆所需消耗的最少精力。