AOJ 153.Redraiment的走法

175

题目



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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论