题目

Description

Redraiment是个聪明人，总是以奇怪的思考方法思考问题，但不知道为什么，他的解答总是最最巧妙，我们隆重地称他为诡异人！
有一天Jesse不经意中发现，诡异人的走路方法很特别，于是特别关注了他的走路规则。他发现诡异人总是往高处走，但走的步数总是最多，不知道为什么？你能替Jesse研究研究他最多走的步数吗？
发现了你也会是个聪明人!^_^

Input

There has several test cases. Each case start with an integer n(0 < n ≤10000), then follows n integers hi, each seperated by a space. 1 ≤ hi ≤ 100),which represents the height of the place.

Output

For each case output a line with the max number of the steps he can go .

Sample Input

5
1 2 3 4 5
6
2 5 1 5 4 5

Sample Output

5
3

Hint

6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5
从第5格开始走最多有2步,4 5

题解

模板题
>最长上升子序列<

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn = 10005;

int dp[maxn];
int a[maxn];

bool  Do() {
    int n;
    if(scanf("%d",&n) == EOF)
        return false;

    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);

    memset(dp,0,sizeof(dp));

    int Max = 0;
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j < i;j++)
            if(a[j] < a[i] || j == 0)
                dp[i] = max(dp[i],dp[j] + 1);
        Max = max(Max,dp[i]);
    }

    printf("%d\n",Max);

    return true;
}

int main() {
    while(Do());
    return 0;
}