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

Southeastern European Regional Programming Contest 2008

#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

第一行输入一个

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
<img src="http://acm.fzu.edu.cn/image/prodesc.gif" alt="LIS"> Problem Description目 暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算，柯南追踪伤害阿笠博士的凶手，根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经 过一系列的推理后，柯南发现受害者的名字均包含扑克牌的数值，且扑克牌的大小是严格递增的，此外遇害者与毛利小五郎有关。
为了避免下一个遇害者的出现，柯南将可能遭到暗算的人中的数字按关联程度排列了出来，即顺序不可改变。柯南需要知道共有多少种可能结果，满足受害人名字出现的数字严格递增，但是他柯南要找出关键的证据所在，所以这个任务就交给你了。
(如果你看不懂上面在说什么，这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。)
<img src="http://acm.fzu.edu.cn/image/prodesc.gif" alt="LIS"> Input多组数据(<=10)，处理到EOF。
第一行输入正整数N(N≤100 000)，表示共有N个人。
第二行共有N个整数Ai(1≤Ai≤10^9)，表示第i个人名字中的数字。
<img src="http://acm.fzu.edu.cn/image/prodesc.gif" alt="LIS"> Output每组数据输出一个整数，表示所有可能的结果。由于结果可能较大，对1 000 000 007取模后输出。
<img src="http://acm.fzu.edu.cn/image/prodesc.gif" alt="LIS"> Sample Input
          3 1 3 2
        
<img src="http://acm.fzu.edu.cn/image/prodesc.gif" alt="LIS"> Sample Output
          5
        
<img src="http://acm.fzu.edu.cn/image/prodesc.gif" alt="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;
}
 

          
       