POJ 3903 Stock Exchange【LIS 二分查找】_非常可乐(이녕)的博客-程序员秘密

技术标签: 二分||三分  二分查找  LIS  poj  动态规划  

Stock Exchange

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 5914   Accepted: 2072

Description

The world financial crisis is quite a subject. Some people are more relaxed while others are quite anxious. John is one of them. He is very concerned about the evolution of the stock exchange. He follows stock prices every day looking for rising trends. Given a sequence of numbers p1, p2,...,pn representing stock prices, a rising trend is a subsequence pi1 < pi2 < ... < pik, with i1 < i2 < ... < ik. John’s problem is to find very quickly the longest rising trend.

Input

Each data set in the file stands for a particular set of stock prices. A data set starts with the length L (L ≤ 100000) of the sequence of numbers, followed by the numbers (a number fits a long integer).
White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

Output

The program prints the length of the longest rising trend.
For each set of data the program prints the result to the standard output from the beginning of a line.

Sample Input

6 
5 2 1 4 5 3 
3  
1 1 1 
4 
4 3 2 1

Sample Output

3 
1 
1

Hint

There are three data sets. In the first case, the length L of the sequence is 6. The sequence is 5, 2, 1, 4, 5, 3. The result for the data set is the length of the longest rising trend: 3.

 

嗯,题意是求最长上升子序列,O(n^2)复杂度会超时吧,这里手写了二分查找。相当于把原序列中的数按顺序插入进去,取代其中第一个比它大或和它相等的数的位置上。

 

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 100010
#define inf 0x3f3f3f3f
using namespace std;
int dp[maxn];
int num[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;++i)
            scanf("%d",&num[i]);
        memset(dp,inf,sizeof(dp));
        num[n]=inf;
        for(int i=0;i<=n;++i)
        {
            int l=0,r=n,rec=0;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(dp[mid]>=num[i])
                {
                    r=mid-1;
                    rec=mid;
                }
                else
                    l=mid+1;
            }
            dp[rec]=num[i];
            if(i==n)
            {
                printf("%d\n",rec);
                break;
            }
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wyjwyl/article/details/51224701

智能推荐

Win10 UWP 开发系列:使用SplitView实现汉堡菜单及页面内导航_bill_live的博客-程序员秘密

在Win10之前,WP平台的App主要有枢轴和全景两种导航模式,我个人更喜欢Pivot即枢轴模式,可以左右切换,非常方便。全景视图因为对设计要求比较高,自己总是做不出好的效果。对于一般的新闻阅读类App来说,Pivot更适合多个频道的展示,因为内容基本都是一样的。到了Win10,微软模仿其他平台也推出了汉堡菜单,但并没有提供现成的控件,而是需要开发者通过一个名为SplitView的控件来实现。...

create-react-app中使用CodeMirror轻量级代码编辑器,实现自动提示,自动补全代码问题___1234的博客-程序员秘密_codemirror 自动补全

构建create-react-app,这里忽略······安装 代码编辑器 CodeMirror 的轻量级 React 组件npm install @uiw/react-codemirror --save安装好了之后,就可以直接引入使用了,直接上代码:import CodeMirror from '@uiw/react-codemirror';import 'codemi...

k/3cloud表格控件块粘贴代码逻辑_范永强的博客-程序员秘密

有些问题BOS不太好处理,例如用户希望枚举全部按名称检索赋值,这个和BOS这边的通用逻辑有冲突。因此将块粘贴代码逻辑贴出来给到大家,大家可以在表单插件EntityBlockPasting事件中自己处理,然后将cancel设置为true。以下代码用户可以参考一下,插件代码中需要将其中一些属性或方法修改,例如this.BusinessInfo替换为this.View.BusinessInfo,Upda

webpack实现css样式对不同浏览器的兼容_JohnKeatinghhh的博客-程序员秘密_css样式在不同浏览器兼容

webpack实现css样式对不同浏览器的兼容1.安装指定版本的 postcss-loader 和 postcss-preset-env2.配置webpack.config.js3.在项目文件的package.json中配置browserslist4. 选择process.env.NODE_ENV5.测试兼容后的代码众所周知,css在不同浏览器中的兼容性问题是一个十分令人头痛的问题,而用webpack工具中的postcss 就可以将打包好的css文件写成兼容一些老浏览器的css环境: "devDep

Linux远程管理器xshell和xftp使用教程_congyh的博客-程序员秘密

Xshell 是一个强大的安全终端模拟软件,它支持SSH1, SSH2, 以及Microsoft Windows 平台的TELNET 协议。Xftp 是一个基于 MS windows 平台的功能强大的SFTP、FTP 文件传输软件。安装完毕后打开xshell设置网站帐号信息设置主机信息设置服务器帐号设置字符集编码

centos6/7单用户模式, 自定义boot安装镜像, 模拟微型linux系统_根哥的博客的博客-程序员秘密

文章目录1,centos 6/7但用户模式cent6cent71,centos 6/7但用户模式使用场景: 忘记密码,系统启动异常(网络配置错误,磁盘挂载异常)cent6#centos6(开机bootloader读取配置文件: /etc/grub.cfg)[[email protected] ~]# ll /etc/grub.conf lrwxrwxrwx. 1 root root 22 1月 2 ...

随便推点

win10备份为wim_电脑:Win10 专业版提取制作方法_weixin_39687881的博客-程序员秘密

准备工作:➤ 制作环境:Win10 操作系统➤ 使用工具:DISM( 系统自带 )、UltraISO 软碟通

Qwt源码解读之QwtPoint3D类_e5Max的博客-程序员秘密

QwtPoint3D 表征二维坐标系中的一个三维点(x, y, z)。代码分析:1、类接口定义:class QWT_EXPORT QwtPoint3D{public: QwtPoint3D(); // 默认构造函数 QwtPoint3D( double x, double y, double z ); // 三个参数的构造函数 QwtPoint3D(

pythonexe系统错误丢失_pythonw.exe应用程序错误_weixin_39610188的博客-程序员秘密

第一次安装python,出师不利,就遇到这么个错误。多方百度无果,在自己“辛勤”努力下,终于安装成功。1、首先介绍一下系统,Windows8.1 企业版 64位,安装python3.6.5 release版,32位、64位都进行了测试。安装64位时显示的是上图,安装32位时提示api-ms-win-crt-runtime-l1-1-0.dll,但是后来不知道怎么也提示上图了。2、然后就开始巴啦啦的...

我使用Feign上传文件踩的坑,MultipartFile文件死活传不过去_HairyCoder的博客-程序员秘密

我使用Feign上传文件踩的坑,MultipartFile文件死活传不过去欢迎使用Markdown编辑器你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了...