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

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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>
#include 
#include 
#include 
#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=1;i<=n;i++)
        cin>>a[i];
    int len=1;//最长子序列长度
    dp[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>dp[len])//大于前一个，则赋值
            dp[++len]=a[i];
        else
        {
            //小于，则找到第一个大于a[i]的值，并把它替代了
            int t=lower_bound(dp+1,dp+len,a[i])-dp;
            dp[t]=a[i];
        }
    }
    cout<endl;
    return 0;
}
动态规划简单dp【POJ】题解

相关

标签