数据结构算法（排序成有序列）

题意

给出一个系列，每次可以把一个元素放到开头或者放到结尾，问最少多少次操作能让他有序。

思路

观察发现每个元素至多操作一次，只需要考虑哪些元素需要操作。
正难则反，我们可以考虑那些元素不需要操作，不需要操作的元素最后一定会相邻，所以他们本身就是要相邻的，
设$b[i]$是离散化过后的数组，我们要找出最长的连续上升子序列，这里的连续指的是相差$1$。有：
$dp[b[i]] = dp[b[i]-1]+1$

代码

#include<bits/stdc++.h> #define ll long long #define N 3005 #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define inf 0x3f3f3f3f #define pb push_back #define mp make_pair #define lowbit(i) ((i)&(-i)) #define VI vector<int> using namespace std; int t,n,a[N],b[N],dp[N]; int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); ios::sync_with_stdio(0); cin.tie(0); cin>>t; while(t--){ cin>>n; rep(i,1,n) cin>>a[i],b[i] = a[i],dp[i]=0; sort(a+1,a+n+1); rep(i,1,n) b[i] = lower_bound(a+1,a+n+1,b[i])-a;//cout << b[i] << ' '; //acout << endl; rep(i,1,n) dp[b[i]] = dp[b[i]-1]+1; cout << n-*max_element(dp+1,dp+n+1) << endl; } return 0; } 

本文地址：https://blog.csdn.net/qq_44062973/article/details/107760237