POJ-2533-Longest Ordered Subsequence(最长递增子序列)

链接:

题意:

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence ( a1, a2, ..., aN) be any sequence ( ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

思路:

维护一个数组, 大于的直接加上去, 小的去更新内部.
nlogn

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
//#include <memory.h>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <sstream>
#define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const LL MOD = 20090717;
const int MAXN = 2e3+10;

int a[MAXN], Dp[MAXN];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 1;i <= n;i++)
        scanf("%d", &a[i]);
    int pos = 0;
    Dp[0] = -1;
    for (int i = 1;i <= n;i++)
    {
        if (a[i] > Dp[pos])
            Dp[++pos] = a[i];
        else
        {
            int p = lower_bound(Dp+1, Dp+1+pos, a[i])-Dp;
            Dp[p] = a[i];
        }
    }
    printf("%d
", pos);

    return 0;
}