最长不下降子序列


题目大意:

给定一个长度为 N 的整数序列:A\(_{1}\),A\(_{2}\),⋅⋅⋅,A\(_{N}\)
现在你有一次机会,将其中连续的 K 个数修改成任意一个相同值。
请你计算如何修改可以使修改后的数列的最长不下降子序列最长,请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列,子序列中的每个数不小于在它之前的数。


题目思路:

我们考虑这样两个数组,f[ ],g[ ],分别表示以i为结尾的最长不下降子序列长度和以i为开始的最长子序列长度,那我们的答案如果在不考虑修改k个数这个条件时,我们的答案就是:f[i]+g[i]-1;

当我们再去考考虑修改k个连续数这个条件时,答案就变成了:max(\(\sum_{i = n}^{i-k>=1}\)f[i-k]+k+g[i],k);

这个答案可以被看为由三部分组成:f[i-k]以i-k为结尾 + 修改后的k个数 + g[i]以i为开始

所以在实现上我们考虑用权值线段树来优化寻找最长不下降子序列这个过程

权值线段树维护的是以离散化后的点为(结束/开始)的最长不下降子序列长度

先将原数据去重+离散化
然后先处理f[i] =query(1,1,tot,1,a[i])+1 ,每次查询query(1,1,tot,1,a[i]),查询在他之前的最长子序列,之后将f[i]插入a[i]的位置

例如:a[i]离散化以后为3,那我们此时的查询即为query(1,1,tot,1,3)
这样我们就是查询从1到3的最长不下降子序列,修改也是同理,将3的值改为max(val,f[i])

之后重建线段树,倒着处理g[i]
几乎是同样的方法,只不过在这个同时处理一下ans = max(ans,f[i-k]+k+g[i]);


代码实现:

# include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
#define ls u<<1
#define rs u<<1|1
int f[N],g[N];//f[]--以i为结尾的最长...,g[]--以i为开始的最长...
int a[N];
int n,k;

struct seg{
    int maxn[4*N];
    void pushup(int u){
        maxn[u] = max(maxn[ls],maxn[rs]);
    }
    void build(int u,int l,int r){
        if(l == r){
            maxn[u] = 0;
            return;
        }
        int mid = l+r>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(u);
    }
    
    void modify(int u,int l,int r,int pos,int val){
        if(l == r){
            maxn[u] = max(maxn[u],val);
            return;
        }
        int mid = l+r>>1;
        if(pos<=mid) modify(ls,l,mid,pos,val);
        else modify(rs,mid+1,r,pos,val);
        pushup(u);
    }
    int query(int u,int l,int r,int L,int R){
        if(l==L&&r==R){
            return maxn[u];
        }
        int mid = l+r>>1;
        if(R<=mid) return query(ls,l,mid,L,R);
        else if(L>mid) return query(rs,mid+1,r,L,R);
        else return max(query(ls,l,mid,L,mid),query(rs,mid+1,r,mid+1,R));
    }
}tr;
int b[N],tot;
int find(int u){
    int l = 1,r = tot;
    int ans;
    while(l<r){
        int mid = l+r>>1;
        if(b[mid] >= u){
            r = mid;
        } 
        else l = mid+1;
    }
    return l;
}

int main(){
    cin>>n>>k;
    for(int i = 1;i <= n;++i) {
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b+1,b+1+n);
    tot = 1;
    for(int i = 2;i <= n;++i)//离散化+去重
    {
        if(b[i] != b[tot]){
            b[++tot] = b[i];
        }
    }
    
    for(int i = 1;i <= n;++i)
    {
        a[i] = find(a[i]);
    }
    tr.build(1,1,tot);//处理f[i]
    for(int i = 1;i <= n-k;++i){
        f[i] = tr.query(1,1,tot,1,a[i])+1;
        tr.modify(1,1,tot,a[i],f[i]);
    }
    
    tr.build(1,1,tot);//处理完f[i]后重建线段树来啊处理g[i]
    int ans = 0;
    for(int i = n;i-k>=1;--i){
        ans = max(ans,f[i-k]+k+tr.query(1,1,tot,a[i-k],tot));
        g[i] = tr.query(1,1,tot,a[i],tot)+1;
        tr.modify(1,1,tot,a[i],g[i]);
        
    }
    cout<<ans<<endl;
    
    
    
    return 0;
}

原文地址:http://www.cnblogs.com/empty-y/p/16847360.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性