AOJ 797.Roll不是处女座

188


题目


点击显/隐题目

一天Roll在codeforces网站上做ACM练习的时候,由于打开题目的顺序比较随性,他看到了他的浏览器标签页是这样的:

虽然Roll不是处女座,但他还是非常地不开心,于是他移动了标签页,就变成了这样:

由此想到了一个问题,对于一个乱序的不重复的数字序列,最少需要移动几个数字,能使它们从小到大排列。
例如序列 4 2 3 1 5,只要把1放到第一个,4放到3和5之间,就变成了1 2 3 4 5





输入数据包含多组
每组数据第一行一个数n (0﹤n≤?1000),表示这个序列有n个数字。
第二行包含n个数字Ai(0≤Ai≤10^9),





对于每组数据输出一个整数,表示最少需要移动几个数字。





5
4 2 3 1 5
2
1 2





2
0





题解


求移动最少的数字使序列递增
首先本身递增的自然就不必再移动了,要想让移动最少就应该先找到 最长上升子序列
套用 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.syncwithstdio(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
lowerbound(ans + 1,ans + 1 + len,node[i]) = node[i];
}

cout<< n - len<}
}

发布评论
  • 点击查看/关闭被识别为广告的评论