ACM模版

描述

题解

猛一看这道题感觉似曾相识，好像以前做过一个只能往前插入的题，具体记不清楚了……

这个问题实际上就是求最长等差数列（子序列）长度，要求 d = 1 即可，如此，复杂度只要为 O(n) 的动态规划就能搞定，get 到了新技能~~~

如果要说为啥只要求最长……就可以得到答案，那么也十分好证明，根据题意，我们只要把这个要求的子序列中间夹杂的多余的数移出去就可以保证这个子序列最后合法，移出去的部分很容易就可以同样合法，这样就考虑分为两部分，一部分是通过移出去而保留下来的必然合法，另一部分则是移出去放在前后两端的必然存在合法的移动方案，那么想要移动的次数最少，变相的就是要求中间保留下来的最长，最后用 N-res 即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 5e4 + 5;

int A[MAXN], pre[MAXN];

int main()
{
    int N;

    while (~scanf("%d", &N))
    {
        memset(pre, 0, sizeof(pre));

        int res = 0;
        for (int i = 1; i <= N; ++i)
        {
            scanf("%d", &A[i]);
            pre[A[i]] = pre[A[i] - 1] + 1;
            res = max(res, pre[A[i]]);
        }
        printf("%d\n", N - res);
    }

    return 0;
}