51nod 1294 修改数组

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

题意:给出一个整数数组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

一条评论

  1. μεταλλικά κρεβάτια και παιδικά έπιπλα στις καλύτερες τιμές της Αγοράς! 2018年11月15日 下午10:54 回复

    Wonderful work! That is the kind of info that should be shared around the net.

    Disgrace on the search engines for now not positioning this publish upper!

    Come on over and seek advice from my web site . Thanks
    =) http://Hd-rulez.info/index.php?task=profile&id=2968292

发表评论

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

Ɣ回顶部