LIS

LIS

1、poj3903–Stock Exchange (LIS)
Stock Exchange
     
     

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.

Source

#include <iostream>
const int N = 100000+100;

using namespace std;

int a[N], f[N], d[N];   //d[i]用于记录以i结尾的严格上升子序列最长长度; 

int bsearch(int f[], int size, int a)
{
    int l=0, r= size-1;
    while(l <= r)
    {
        int mid=(l+r)>>1;
        if(a >f[mid-1] && a<= f[mid]) return mid; // a >=f[mid] && a< f[mid];
        else if(a <f[mid]) r= mid-1;
        else l= mid+1;
    }
}
int LIS(int a[], int n)
{
    int j, size= 1;
    f[0]= a[0]; d[0]= 1;
    for(int i=1; i< n; i++)
    {
        if(a[i] <= f[0]) j= 0;               // < 
        else if(a[i] >f[size-1]) j= size++;  // >= 
        else j =bsearch(f, size, a[i]);
        f[j]= a[i]; d[i]= j+1;
    }
    return size;
}
int main()
{
    int n; 
    while(scanf("%d", &n) != EOF)
    {
        for(int i=0; i< n; i++) 
            scanf("%d", &a[i]);
        LIS(a, n); //int maxL= LIS(a, n); 
        int maxL= 0;
        for(int i=0; i< n; i++)
            maxL=max(maxL, d[i]);
        printf("%d\n", maxL);
    }
    return 0;    
}

LIS变形 hdoj5256

序列变换

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

我们有一个数列A1,A2…An,你现在要求修改数量最少的元素,使得这个数列严格递增。其中无论是修改前还是修改后,每个元素都必须是整数。

请输出最少需要修改多少个元素。
 

Input

第一行输入一个
T (1 \leq T \leq 10),表示有多少组数据

每一组数据:

第一行输入一个N (1 \leq N \leq 10^5),表示数列的长度

第二行输入N个数A_1, A_2, …, A_n

每一个数列中的元素都是正整数而且不超过10^6

 

Output

对于每组数据,先输出一行

Case #i:

然后输出最少需要修改多少个元素。

 

Sample Input

2 2 1 10 3 2 5 4

 

Sample Output

Case #1: 0 Case #2: 1
对原数组处理一下 a[i]-i; 求非严格上升子序列个数; 然后输出最少需要修改多少个元素。
#include <iostream>
const int N = 100000+100;

using namespace std;

int a[N], f[N], d[N];   

int bsearch(int f[], int size, int a)
{
    int l=0, r= size-1;
    while(l <= r)
    {
        int mid=(l+r)>>1;
        if(a >= f[mid-1] && a< f[mid]) return mid;
        else if(a <f[mid]) r= mid-1;
        else l= mid+1;
    }
}
int LIS(int a[], int n)
{
    int j, size= 1;
    f[0]= a[0]; d[0]= 1;
    for(int i=1; i< n; i++)
    {
        if(a[i] < f[0]) j= 0;               
        else if(a[i] >= f[size-1]) j= size++;   
        else j =bsearch(f, size, a[i]);
        f[j]= a[i]; d[i]= j+1;
    }
    return size;
}
int main()
{
    
    int n, Q=1; int t; scanf("%d", &t); 
    while( t--)
    {scanf("%d", &n);
        for(int i=0; i< n; i++) 
        {
            scanf("%d", &a[i]); a[i]-= i;
        }    
        LIS(a, n); 
        int maxL= 0;
        for(int i=0; i< n; i++)
            maxL=max(maxL, d[i]);
        printf("Case #%d:\n%d\n", Q++, n- maxL);
    }
    return 0;    
}

 3、

第十四个目标

Accept: 14    Submit: 26
Time Limit: 1000 mSec    Memory Limit : 32768 KB

LIS Problem Description

目 暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算,柯南追踪伤害阿笠博士的凶手,根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经 过一系列的推理后,柯南发现受害者的名字均包含扑克牌的数值,且扑克牌的大小是严格递增的,此外遇害者与毛利小五郎有关。

为了避免下一个遇害者的出现,柯南将可能遭到暗算的人中的数字按关联程度排列了出来,即顺序不可改变。柯南需要知道共有多少种可能结果,满足受害人名字出现的数字严格递增,但是他柯南要找出关键的证据所在,所以这个任务就交给你了。

(如果你看不懂上面在说什么,这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2),共5个。长得一样的但是位置不同的算不同的子序列,比如数列(3,3)的答案是2。)

LIS Input

多组数据(<=10),处理到EOF。

第一行输入正整数N(N≤100 000),表示共有N个人。

第二行共有N个整数Ai(1≤Ai≤10^9),表示第i个人名字中的数字。

LIS Output

每组数据输出一个整数,表示所有可能的结果。由于结果可能较大,对1 000 000 007取模后输出。

LIS Sample Input

3 1 3 2

LIS Sample Output

5

LIS Source

福州大学第十三届程序设计竞赛

//树状数组+dp+离散化 ; 
#include<cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mx = 100005;
const int mod = 1000000007;

int tree[mx], a[mx], dis[mx], n;

///从右下往左上“看”
bool cmp(int x, int y)
{
    if (a[x] != a[y]) return a[x] < a[y];
    return x > y;
}

void add(int pos, int x)
{
    for (; pos <= n; pos += pos & -pos)
        tree[pos] = (tree[pos] + x) % mod;
}

int sum(int pos)
{
    int res = 0;
    for (; pos; pos -= pos & -pos) res = (res + tree[pos]) % mod;
    return res;
}

int main()
{
        while(scanf("%d", &n) != EOF)
        {
            for (int i = 1; i <= n; ++i) 
                scanf("%d", &a[i]), dis[i] = i;
            sort(dis + 1, dis + n + 1, cmp);
            memset(tree, 0, sizeof(tree));
            for (int i = 1; i <= n; i++) 
                add(dis[i], sum(dis[i]) + 1);
            printf("%d\n", sum(n));
        }
    return 0;
}

 

 

转载于:https://www.cnblogs.com/soTired/p/5438584.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/109051.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 解决网页文字无法选中或复制的方法_复制不了的文字

    解决网页文字无法选中或复制的方法_复制不了的文字我们在查看一些网页时会遇到不能复制的问题,或者鼠标无法选中文字,导致不能复制。这时候我们按下键盘的F12,点击console控制台,输入以下代码后回车即可vareles=document.getElementsByTagName(‘*’);for(vari=0;i<eles.length;i++){eles[i].style.userSele…

    2022年10月13日
    2
  • fiddler进行弱网测试

    使用Fiddler对手机App应用进行抓包,可以对App接口进行测试,也可以了解App传输中流量使用及请求响应情况,从而测试数据传输过程中流量使用的是否合理。抓包过程:1、Fiddler设置1)启动Fiddler->Tools->FiddlerOptions2)HTTPS选项卡中,设置如下,勾选过程中如有弹窗允许即可;Connections选项卡中,勾选Allowre…

    2022年4月6日
    364
  • Scala中 fastjson Object转JsonObject

    Scala中 fastjson Object转JsonObjectScala中,fastjson的Object转JsonObject相比于Java有些差别,不支持像Java一样强转。//java中Object转JsonObjectJSONObjectjsonObject=(JSONObject)JSON.toJSON(eventBean);导包<!–阿里巴巴开源json解析框架–><dep…

    2022年4月29日
    182
  • struts2核心控制器在哪里配置_intercontrol控制器

    struts2核心控制器在哪里配置_intercontrol控制器原文:http://mopishv0.blog.163.com/blog/static/54455932200981295843192/1.   在struts1.x系列中,所有的请求是通过一个servlet(ActionServlet)来管理控制的,在Struts2.X而是经过一个Filter来处理请求的。Struts2将核心控制器设计成Filter,而不是一个普通Servlet。struts1.x中actionorg.apache.struts.action.ActionServlet。。。St

    2022年8月16日
    7
  • excel从右向左截取字符串函数的值_从后往前截取字符串用什么函数

    excel从右向左截取字符串函数的值_从后往前截取字符串用什么函数从A串中提取从”.”开始的字符串B,可以使用find函数来对”.”的首次出现进行定位,这类似于各种语言中的indexOf功能,find是从左往右查找的,在EXCEL中并没有从右往左查找,类似lastIndexOf的函数.在EXCEL想要从右往左截取字符,可使用公式=TRIM(RIGHT(SUBSTITUTE(A1,”/”,REPT(“”,LEN(A1))),LEN(A1))).例:已知A

    2025年6月5日
    2
  • 怎么将方波转化为正弦波(正弦波变成方波的原理)

    一、题目要求:1、使用555做出脉冲方波2、使用TL084运放做出方波和锯齿波3、使用TLM314稳压做直流偏置4、方波要求峰峰值为1V,正弦波要求峰值为0~2V,锯齿波要求峰峰值为1V。二、解题流程1、使用555做出脉冲方波(1)参数计算(2)仿真设计图:(3)仿真波形(4)实际操作中总结的经验A、一个滑动变阻器十分的重要,我们需要购入一个,在正式比赛的时候。(如果要参加比赛,我们自己买一…

    2022年4月18日
    205

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号