【POJ - 2533】Longest Ordered Subsequence （最长上升子序列 简单dp）

时间：2022-02-16 23:57:17

Longest Ordered Subsequence

搬中文

Descriptions:

给出一个序列，求出这个序列的最长上升子序列。

序列A的上升子序列B定义如下：

  1. B为A的子序列
  2. B为严格递增序列

Input

第一行包含一个整数n，表示给出序列的元素个数。

第二行包含n个整数，代表这个序列。
1 <= N <= 1000

Output

输出给出序列的最长子序列的长度。

Sample Input

7

1 7 3 5 9 4 8

Sample Output

4

题目链接：

https://vjudge.net/problem/POJ-2533

就是最长子序列，没啥说的，简单dp

二分查找的函数有 3 个：
lower_bound(起始地址，结束地址，要查找的数值) 地址：前闭后开。返回的是第一个大于或等于数值出现的位置，如果数值大于数组中全部元素，返回的是结束地址。
upper_bound(起始地址，结束地址，要查找的数值) 地址：前闭后开。返回的是第一个大于数值出现的位置，如果数值大于数组中全部元素，返回的是结束地址。
binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x, y) memset(x, y, sizeof(x))

#define Maxn 1000+10

using namespace std;

int dp[Maxn];

int a[Maxn];

int main()

{

    int n;

    cin>>n;

    for(int i=;i<=n;i++)

        cin>>a[i];

    int len=;//最长子序列长度

    dp[]=a[];

    for(int i=;i<=n;i++)

    {

        if(a[i]>dp[len])//大于前一个，则赋值

            dp[++len]=a[i];

        else

        {

            //小于，则找到第一个大于a[i]的值，并把它替代了

            int t=lower_bound(dp+,dp+len,a[i])-dp;

            dp[t]=a[i];

        }

    }

    cout<<len<<endl;

    return ;

}

相关文章