洛谷3411 - 序列变换

题意

给定一个长度为N的数列Ai。
你可以对数列进行若干次操作,每次操作可以从数列中任选一个数,把它移动到数列的开头或者结尾。
求最少经过多少次操作,可以把数列变成单调不减的。“单调不减”意味着数列中的任意一个数都不大于排在它后边的数。

分析

你可以把题意转化为:找到一个不降子序列,使得未选中的数必须不处于子序列的最小值和最大值之间(理由:小于等于最小值的可以移到前面去,大于等于最大值的可以移到后面去)
即找到一个值的区间[L, R],在其中选择一个不降子序列,使得其包含了区间(L, R)中的所有值。
[L, R]表示闭区间,(L, R)表示开区间!)

那么你只要维护一个答案队列,使得其满足题意。每次考虑扩展右区间,同时检查可行性,更新最优解。
需要注意的是,新增的节点值相同时可能会互相产生干扰,我们应当考虑倒序检查,之后顺序入队。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×