codeforces 605 A. Sorting Railway Cars (dp)

题目链接

题意:给出一个n个数的排列,每次可以把一个数放到最前面或者最后面的位置,问至少要进行多少次操作才能使得数列升序。

思路:考虑不被移动的那些数,当把所有一定的数去掉以后,这些剩下的数一定是一段数值连续,位置递增的数。如果想要移动的数最少,俺么这串递增的数就尽可能长。

dp[a[i]] = dp[a[i]-1] + 1

那么ans = n – max{dp[i]}

另外:对于要移动的数,我们可以按照一定顺序(放在前面的数按照递减顺序,放在最长序列后面的数按照递增顺序)移动,可以保证每个数只需要移动一次。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz