51nod 1294 修改数组

作者: MayFlyyh 分类: DP 发布时间: 2018-10-23 07:29 ė 6 没有评论

题意:给出一个整数数组A,你可以将任何一个数修改为任意一个正整数,最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数?

n<=100000,0<=a[i]<=10^9


因为新生成的数列必须是正整数,那么第一个数必至少为1,同样,每个数在新生成的数列中至少应该为下标。。

那么除去那些值小于自身下标的,剩下的数从取值方面没问题,但有可能不递增,所以我们保留一个最长不下降子序列就可以了。

首先,最长不下降子序列的值显然满足条件,我们思考那些刚才被除去的值为什么可以插进来。

b[i]=a[i]-i

b[j]=a[j]-j

i+x<j

b[i]<=b[j]

a[i]-i<=a[j]-j

j-i<=a[j]-a[i]

j-i>x

显然,如果b[i]和b[j]属于这个最长不下降子序列,那么中间必是有一个值可以被添加的。(如果下标间隔为x,那中间就一定可以放x个值)

#include<bits/stdc++.h>
const int N = 101000;
int a[N],b[N],n,ans,t,m;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),b[i]=a[i]-i;
    for(int i=1;i<=n;++i)
        if(b[i]>=0) a[++m]=b[i];
    if(!m) ans=n;
    else{
        b[t=1]=a[1];
        for(int i=2;i<=m;++i){
            if(a[i]>=b[t]){
                b[++t]=a[i];
            }
            else{
                int s=std::upper_bound(b+1,b+1+t,a[i])-b;
                b[s]=a[i];
            }
        }
        ans=n-t;
    }
    printf("%d\n",ans);
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/417

0

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部