NYOJ 214 单调递增子序列(二)

点击打开链接NYOJ 214

1题目：
单调递增子序列(二)
描述
给定一整型数列{a1,a2...,an}（0<n<=100000），找出单调递增最长子序列，并求出其长度。
如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。
输入
有多组测试数据（<=7）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的下一行里有n个整数，表示数列中的所有元素.每个整形数中间用空格间隔开（0<n<=100000）。
数据以EOF结束 。
输入数据保证合法（全为int型整数）！
输出
对于每组测试数据输出整形数列的最长递增子序列的长度，每个输出占一行。
样例输入
7
1 9 10 5 11 2 13
2
2 -1
样例输出
5
1

2思路：DP（最长上升子序列）
3分析：
1dp[i]表示以第i个元素为结尾的最长的长度，tmpNum[i]表示递增子序列长度为i的最后一个值的最小值，那么就有tmpNum[1]< tmpNum[2]<......<tmpNum[k],k为最长的长度。
2那么我们每次就可以根据当前的元素num[i]在tmpNum数组中的位置j来确定当前的dp[i]。如果当前的num[i]在tmpNum数组中最小即j = 0，那么dp[i] = 1，tmpNum[1] = num[i] ; 否则dp[i] = j； tmpNum[j] = num[i];
3确定num[i]在tmpNum数组中的位置用STL 中的lower_bound()；返回第一个>=num[i]的迭代器。
4样例分析：例如 2 1 2，那么首先初始化tmpNum[0] = tmpNum[1] = ..... = INF;
num[0] = 2 ; 这个时候num[0]比tmpNum数组中的任何值都小，所以j = 1 ， 那么更新后 tmpNum[0] = INF , tmpNum[1] = 2 .....
num[1] = 1 ; 这个时候num[1]比tmpNum数组中的任何值都小，所以j = 1 ， 那么更新后 tmpNum[0] = INF , tmpNum[1] = 1 ......
num[2] = 2 ; 这个时候num[2]比tmpNum数组中tmpNum[2]小，所以j = 2 ， 那么更新后 tmpNum[0] = INF , tmpNum[1] = 1 tmpNum[2] = 2.....

4代码：

#include <algorithm>  #include <iostream> #include <cstring>#include <cstdio>using namespace std;#define MAXN 100010#define INF 0xFFFFFFFint n , ans;int num[MAXN];int tmpNum[MAXN];int dp[MAXN];void solve() {    memset(dp , 0 , sizeof(dp)) ; ans = 0;    for(int i = 0 ; i < n ; i++) tmpNum[i] = INF;    for(int i = 0 ; i < n ; i++){        int j = lower_bound(tmpNum , tmpNum+n , num[i])-tmpNum;        if(!j) j = 1;         dp[i] = j;        tmpNum[j] = num[i];        if(ans < dp[i]) ans = dp[i];    }    printf("%d\n" , ans);}int main() {    //freopen("input.txt", "r", stdin);    while(scanf("%d%*c" , &n) != EOF){        for(int i = 0 ; i < n ; i++)            scanf("%d" , &num[i]);        solve();    }    return 0;}