POJ 1631 Bridging signals（LIS的等价表述）-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

POJ 1631 Bridging signals（LIS的等价表述）

阅读量：6426 次

发布时间：2019-06-23

本文共 758 字，大约阅读时间需要 2 分钟。

把左边固定，看右边，要求线不相交，编号满足单调性，其实是LIS的等价表述。

（如果编号是乱的也可以把它有序化就像Uva 10635 Prince and Princess那样

O(nlogn)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                //#include
                
                 using namespace std;const int maxn = 4e4+5;int g[maxn];//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int T; cin>>T; while(T--){ int n, ans = 0; scanf("%d",&n); for(int i = 0,c = 1; i < n; i++){ int x, k; scanf("%d",&x); k = lower_bound(g+1,g+c,x)-g; ans = max(ans,k); g[k] = x; if(k==c) c++; //不用把辅助数组g初始化，只要维护一个下标即可 } printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/jerryRey/p/4887319.html

你可能感兴趣的文章

透视美国大数据爆发全景

java学习第一天1.2

清空输入缓冲区的方法

Yii2 项目优化小贴士

UIScrollView的判断位置的属性如下：

Applicatin Loader上传app步骤记录

两种方法修改table表的内容

张小龙莫慌马化腾莫急你们要好好的微信还有时间

一些常用软件静默安装参数(nsis,msi,InstallShield ,Inno)

部署mimic版本的Ceph分布式存储系统

IIS SSL客户端证书（忽略/接受/必须）之三——思考验证（1）

Angular 文档中链接的修改路径

JTable内容居中显示

MySQL内置help解析（SQL语句说明书）

使用Mybatis-Generator自动生成Dao、Model、Mapping相关文件

vShield App设计指南[中]

跟我一起数据挖掘（20）——网站日志挖掘

在Solaris 下使用Os Watcher 监控Oracle

1.9 使用PuTTY远程连接Linux；1.10 使用xshell连接Linux；1.11 PuT

[unity3d]为我们的游戏添加好看的字体

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2025-01-16 01:05:38 当前IP: 3.144.117.164 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我