POJ-2533 Longest Ordered Subsequence

http://poj.org/problem?id=2533

该题是最裸的LIS题，这里有两种方法。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[10000], dp[10004];

int main()
{
int N;
while (scanf("%d", &N) == 1)
    {
int ans = 1, m;
for (int i = 0; i < N; ++i)
        {
            scanf("%d", a+i); 
        }
        dp[0] = 1;
for (int i = 1; i < N; ++i)
        {
            m = 0;
for (int j = 0; j < i; ++j)
            {
if (a[i] > a[j] && dp[j] > m)
                {
                    m = dp[j];
                }
            }
            dp[i] = m+1;
            ans = max(ans, dp[i]);
        } 
        printf("%d\n", ans);
    } 

}

二分优化后的写法，数组c[i]保留长度为i的上升串的末尾最小元素。

代码如下：

#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MAXN 10000
using namespace std;

int a[MAXN+5];

int bsearch(int *c, int l, int r, int val)
{
int mid;
while (l <= r)
    {
        mid = (l+r)>>1;
if (val > c[mid])
            l = mid + 1;
else if (val < c[mid])
            r = mid - 1;
else  // 如果不是严格的递增序列的话，二分查找时，相等视为后者比其大
            return mid;
    }
return l;
}

int LIS(int *a, int N)
{
int c[MAXN], size = 1, pos;
    c[1] = a[0];
for (int i = 1; i < N; ++i)
    {
if (a[i]>c[size])
            pos = ++size;
else
            pos = bsearch(c, 1, size, a[i]);
// 返回比该值稍微大的点
        c[pos] = a[i];
    }
return size;
}

int main()
{
int N;
while (scanf("%d", &N) == 1)
    {
for (int i = 0; i < N; ++i)
        {
            scanf("%d", &a[i]);
        }
        printf("%d\n", LIS(a, N));
    }
}