Roll不是处女座

Time Limit: 2000 ms   Case Time Limit: 2000 ms   Memory Limit: 128 MB Total Submission: 75   Submission Accepted: 6 Description 一天Roll在codeforces网站上做ACM练习的时候，由于打开题目的顺序比较随性，他看到了他的浏览器标签页是这样的： 虽然Roll不是处女座，但他还是非常地不开心，于是他移动了标签页，就变成了这样: 由此想到了一个问题，对于一个乱序的不重复的数字序列，最少需要移动几个数字，能使它们从小到大排列。 例如序列 4 2 3 1 5，只要把1放到第一个，4放到3和5之间，就变成了1 2 3 4 5 Input 输入数据包含多组 每组数据第一行一个数n (0﹤n≤ 1000)，表示这个序列有n个数字。 第二行包含n个数字Ai(0≤Ai≤10^9), Output 对于每组数据输出一个整数，表示最少需要移动几个数字。 Sample Input OriginalTransformed 5 4 2 3 1 5 2 1 2 5[EOL]  4[SP]2[SP]3[SP]1[SP]5[EOL]  2[EOL]  1[SP]2[EOL]  [EOF]  Sample Output OriginalTransformed

20

#include<cstdio> #include<cmath> #include<cstring> #include<string> #include<iostream> #include<algorithm> #include<queue> #include<stack> const int maxn = 1005; //#define DEBUG int a[maxn]; using namespace std; int main() { #ifdef DEBUG freopen("Text.txt", "r", stdin); #endif // DEBUG cin.tie(0); cin.sync_with_stdio(false); int n, best,d[maxn]; while (cin >> n) { int i, j; for (i = 1; i <= n; i++) cin >> a[i]; best = 0; for (i = 1; i <= n; i++) { d[i] = 1; for (j = 1; j <= i; j++) { if (a[i] > a[j] && d[j] + 1 > d[i]) d[i] = d[j] + 1; } } for (i = 1; i <= n; i++) if (d[i] > best) best = d[i]; cout << n - best << endl; } return 0; }