[2014-10-30 模拟赛] Incr (incr.cpp/c/pas)

2014-10-30
竞赛题解 / 动态规划
NOIP模拟赛

描述 Description

数列 A1,A2,…,AN，修改最少的数字，使得数列严格单调递增。

输入格式 InputFormat

第 1 行，1 个整数 N
第 2 行，N 个整数 A1,A2,…,AN

输出格式 OutputFormat

1 个整数，表示最少修改的数字

样例输入 SampleInput

3
1 3 2

样例输出 SampleOutput

1

NOIP 模拟赛

代码 Code

按照每个点的数字减去下标作为关键字求最长不降子序列。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define pa pair<int,int>
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k,z,y,x;
int a[100005];
vector <pa> v;
vector <pa>::iterator iter;
pa p;
inline bool comp(pa a,pa b)
{
    return (b.first-b.second>=a.first-a.second);
}
int main()
{
    freopen("incr.in","r",stdin);
    freopen("incr.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    v.push_back(make_pair(-inf,0));
    for (i=1;i<=n;i++)
    {
        p=make_pair(a[i],i);
        if (v.back().first<a[i] && comp(v.back(),p)) v.push_back(p);
        else
        {
            iter=lower_bound(v.begin(),v.end(),p,comp);
            if (iter!=v.end()) *iter=p;
        }
    }
    printf("%d\n",n-v.size()+1);
    return 0;
}