题面

迷の有序序列
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
n个数，每次可以选择其中一个数移动到序列任意位置。 至少操作几次能让该序列有序

Input
多组输入，输入到文件结束。 每组输入一个正整数n(0 < n <= 1000) 之后一行输入n个正整数xi(0 < xi < 10^9)，表示原始序列

Output
对于每组输入，输出一个整数，表示让序列变为有序所需要的最少操作次数 Hint: 第三组可以选择把1移到2前
也可以把2移动到1后

Example Input
3
1 2 3
3
3 2 1
3
2 1 3

Example Output
0
0
1

Author
LeiQ

所需基础

动态规划 - 最长上升子序列　

解题思路

本题初看可能有些没有头绪，但是仔细想一下的话，由于这道题中元素的移动是任意移动，因此我们只需要把序列中「破坏有序」的这部分元素移动到合适的位置即可，也就是说，其实我们只需求出最长不降子序列和最长不升子序列中的较大值，那么剩下的元素数量就是「破坏有序」的元素的数量，即要交换的元素数量。这样，本题就可以转化为最长不降子序列问题，只需要把最长上升子序列算法中的判定条件加上等于即可。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(int argc, char const *argv[]) {
    int n, a[1000], b[1000], dp1[1000], dp2[1000];
    while(~ scanf("%d", &n)) {
        for(int i=0; i<n; ++i) {
            scanf("%d", &a[i]);
            b[n-1-i] = a[i];
        }
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));
        dp1[0] = dp2[0] = 1;
        // 分别求正序和倒序的最长不降子序列
        for(int i=1; i<n; ++i) {
            int m1 = 0, m2 = 0;
            for(int j=0; j<i; ++j) {
                if(a[j]<=a[i] && m1<dp1[j])
                    m1 = dp1[j];
                if(b[j]<=b[i] && m2<dp2[j])
                    m2 = dp2[j];
            }
            dp1[i] = m1 + 1;
            dp2[i] = m2 + 1;
        }
        int max_len = 0;
        for(int i=0; i<n; ++i) {
            max_len = max(max_len, dp1[i]);
            max_len = max(max_len, dp2[i]);
        }
        printf("%d\n", n-max_len);
    }
    
    return 0;
}