CF1437E Make It Increasing

作者: MayFlyyh 分类: DP 发布时间: 2020-11-03 18:45 ė 6 没有评论

CF1437E Make It Increasing

给你一个数列 a ,一个集合 b , 对于每个 b 中的元素xa_x 不能修改,其他都可以修改,问最少多少次可以将 a 修改为严格单调递增的。如果不存在,输出 -1 。

a 中的所有元素在任意时刻必须都是整数。

首先先判断是否合法,要保证两个不能改变的数a_{b_i}a_{b_{i+1}}之间够不够放下b_{i+1}-b_i个数

if(a[b[i+1]]-a[b[i]]<b[i+1]-b[i])
    puts("-1");//放不下

然后考虑,如果要让序列递增,那么必有
a_{i+1}-a_i\geq 1

a_{i+1}-a_i\geq i+1-i
那么就是
a_{i+1}-(i+1)\geq a_i-i
那么我们令c_i=a_i-i,我们想使修改的数的尽量少,就要在原序列找到一个**包含所有不可修改的数 **(a_{b_i})的最长不下降子序列。

由于这个限制条件,必须在 nlognLIS 的方法下作出修改。

for(int i=1;i<=n;++i){
        if(!top||a[i]>=q[top]){
            q[++top]=a[i];
            if(i==b[t]){
                ++t;
                lb=top;
            }
        }
        else{
            int p=std::upper_bound(q+1,q+1+top,a[i])-q;
            if(p<=lb)   
                continue;
            q[p]=a[i];
            if(b[t]==i){
                ++t;
                lb=p;
                top=p;
            }
        }
    }

记录前一个必须包含的数的坐标为 lb ,如果当前的数a_i当前的可以接在子序列后,就直接接,如果受到限制,就记录。

如果不可以接,考虑更新最长子序列的数组。

在原数组中找到比a_i大的第一个数,记录下标为p

如果 plb 前面,由于a_{lb}>a_i,所以当前数不可更新子序列q数组。

然后可以考虑更新子序列q数组

如果当前的数是受限制的,那么子序列从当前数字后的数必须全部舍去(因为这个数必须加入子序列数组,如果不舍去,子序列就不是不下降的了)此时p成为了子序列数组的最后一个数。

#include<bits/stdc++.h>
const int N = 5e5+10;
int a[N],b[N],t=1,q[N],top=0;
int n,m,lb;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i){
        scanf("%d",&b[i]);
    }
    std::sort(b+1,b+1+m);
    for(int i=1;i<=m-1;++i){
        if(a[b[i+1]]-a[b[i]]<b[i+1]-b[i]){
            puts("-1");
            return 0;
        }
    }
    for(int i=1;i<=n;++i)
        a[i]-=i;
    for(int i=1;i<=n;++i){
        if(!top||a[i]>=q[top]){
            q[++top]=a[i];
            if(i==b[t]){
                ++t;
                lb=top;
            }
        }
        else{
            int p=std::upper_bound(q+1,q+1+top,a[i])-q;
            if(p<=lb)   
                continue;
            q[p]=a[i];
            if(b[t]==i){
                ++t;
                lb=p;
                top=p;
            }
        }
    }
    printf("%d",n-top);
    return 0;
} 

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

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

0

发表评论

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

Captcha Code

Ɣ回顶部