学步园

这题是一DP题，开始我听小白的直接暴力，结果测试数据能过，但提交就wa，我哭啊，呜~~~~，我重敲了一次，结果还是悲剧，几个小时啊，我就在这悲剧，最后翻出小晨的代码，发现好简单的，百度上说是最长上升子序列，于是直接1A了，最长上升子序列就是在一个数列a1-an中，从中选取几个数，这个数组成的序列递增，并且是a1到an中这样子序列中最长那一个。这个题其实也符合最长上升子序列，只要后面有一个比前面高的，就要加一个拦截系统（要增加一个拦截系统，首先要知道前面已经有多少涛拦截系统）。//这个能A

#include<stdio.h>
int n,dis[100000],max,dp[100000];
void DP( )
{
     
           for( int i = 1; i <= n; ++i )
           {
                dp[i] = 1;
                for( int j = 1; j < i; ++j )
                     if( dis[i] > dis[j] && dp[j] + 1 > dp[i] )
                         dp[i] = dp[j] + 1;
                if( dp[i] > dp[max]  )
                    max = i;
            }     
 }     
int main( )
{
    int t;
    while( scanf( "%d",&n ) != EOF )
    {
           max = 0;
           dis[0] = dp[0] = 0;
           for( int i = 1; i <= n; ++i )
                scanf( "%d",&dis[i] );
           DP(); 
            printf( "%d\n",dp[max] );
           }
    return 0;
}