51nod1241 lis变形

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1241

1241 特殊的排序

题目来源： 摩根斯坦利的比赛题

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

收藏

关注

一个数组的元素为1至N的整数，现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个数字，才能完成整个排序过程？

例如：

2 5 3 4 1 将1移到头部 => 

1 2 5 3 4 将5移到尾部 =>

1 2 3 4 5 这样就排好了，移动了2个元素。

 

给出一个1-N的排列，输出完成排序所需的最少移动次数。

Input

第1行：1个数N(2 <= N <= 50000)。
第2 - N + 1行：每行1个数，对应排列中的元素。

Output

输出1个数，对应所需的最少移动次数。

Input示例

5
2
5
3
4
1

Output示例

2
  一开始想到了计算LIS然后输出总长度减去他得值，后来WA了- - 这样是存在反例的，例如2 1 3这样算的话需要1次实际上需要两次。
如果两个lis里的元素大小差距不是1得话说明中间还有其他的元素，那么其中必有一个元素需要移动，所以计算lis是不对的。
我们要找的其实是数字大小连续的最长上升序列。
  数据不大直接dp就好了，令f[i]表示以i为结尾元素的最大连续上升子序列的大小，显然f[i]=f[i-1]+1;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int a[50005];
int f[50005],g[50005];
int main()
{
    int N,i,j,k;
    cin>>N;
    for(i=1;i<=N;++i) scanf("%d",&a[i]);
    memset(f,0,sizeof(f));
    int res=0;
    for(i=1;i<=N;++i)
    {
        f[a[i]]=f[a[i]-1]+1;
        res=max(res,f[a[i]]);
    }
    cout<<N-res<<endl;
    return 0;
}