这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% raw %}
{% endraw %} 一天Roll在codeforces网站上做ACM练习的时候，由于打开题目的顺序比较随性，他看到了他的浏览器标签页是这样的：
虽然Roll不是处女座，但他还是非常地不开心，于是他移动了标签页，就变成了这样:
由此想到了一个问题，对于一个乱序的不重复的数字序列，最少需要移动几个数字，能使它们从小到大排列。
例如序列 4 2 3 1 5，只要把1放到第一个，4放到3和5之间，就变成了1 2 3 4 5
{% raw %}
{% endraw %}
输入数据包含多组
每组数据第一行一个数n (0﹤n≤?1000)，表示这个序列有n个数字。
第二行包含n个数字Ai(0≤Ai≤10^9),
{% raw %}
{% endraw %}
对于每组数据输出一个整数，表示最少需要移动几个数字。
{% raw %}
{% endraw %}
5
4 2 3 1 5
2
1 2
{% raw %}
{% endraw %}
2
0
{% raw %}
题解
求移动最少的数字使序列递增
首先本身递增的自然就不必再移动了,要想让移动最少就应该先找到 最长上升子序列
套用 dp 模板即可
然后剩下的数字都是需要移动的,要最少只需要一次将他们放到最终位置.
也即答案为 n - dp
代码
```cpp Roll不是处女座 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 #include
#include #include #include using namespace std;const int maxn = 1005;
int node[maxn];
int ans[maxn];
int main(){
cin.tie(0);
cin.sync_with_stdio(false);
int n;
while(cin>>n){
for(int i=1;i<=n;i++)
cin>>node[i];
int len = 1;
ans[1] = node[1];
for(int i = 2; i <= n; ++i) {
if(node[i] > ans[len])
ans[++len] = node[i];
else
*lower_bound(ans + 1,ans + 1 + len,node[i]) = node[i];
}
cout<< n - len<<endl;
}
}
</div>