UVALive 6947 Improvements(DP+树状数组)

发布时间:2016-12-6 7:15:52编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVALive 6947 Improvements(DP+树状数组) ",主要涉及到UVALive 6947 Improvements(DP+树状数组) 方面的内容,对于UVALive 6947 Improvements(DP+树状数组) 感兴趣的同学可以参考一下。

【题目链接】

 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4959

 

【题目大意】

  给出一些飞船的位置,每艘飞船用绳子和序号相邻的飞船相连,现在去掉一些飞船,使得飞船之间的绳子不交叉。

【题解】

  绳子不交叉的情况就是可以有两条不交叉的路线来回,我们将位置序列转化为以位置为下标的编号序列,那么题目就转化为求先增后减的最长序列,那么,我们dp正反各求一遍LIS,保存在每个位置,将每个位置两次的答案求和,取最大值就是答案了。

【代码】

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200005;
int n,x,a[N],c[N],up[N],down[N];
int add(int x,int num){while(x<N)c[x]=max(c[x],num),x+=x&-x;}
int query(int x){int s=0;while(x)s=max(s,c[x]),x-=x&-x;return s;}
int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)scanf("%d",&x),a[x]=i;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)add(a[i],up[i]=query(a[i])+1);
        memset(c,0,sizeof(c));
        for(int i=n;i;i--)add(a[i],down[i]=query(a[i])+1);
        int ans=0;
        for(int i=1;i<=n;i++)ans=max(up[i]+down[i]-1,ans);
        printf("%d\n",ans);
    }return 0;


上一篇:LVS集群之NAT模式实现
下一篇:MySQL 5.7基于组提交的并行复制

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款