题目

{% 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 %}

{% endraw %}

题解

求移动最少的数字使序列递增
首先本身递增的自然就不必再移动了,要想让移动最少就应该先找到 最长上升子序列
套用 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>

AOJ 797.Roll不是处女座

题目

题解

代码