wikioi 1576 最长严厉上升子序列

wikioi 1576 最长严格上升子序列

题目描述 Description

非常经典的问题，拿来给大家练手了。 

序列 { 1,2,...,n } 的一个子序列是指序列 { i1, i2, ……, ik },其中 1<=i1 < i2 < …… < ik<=n, 序列 { a1, a2, ……, an } 的一个子序列是指序列 { ai1, ai2, ……, aik },其中 { i1, i2, ……, ik } 是 { 1, 2, ……, n } 的一个子序列.同时,称 k 为此子序列的长度. 

如果 { ai1, ai2, ……, aik } 满足 ai1 ≤ ai2 ≤ …… ≤ aik,则称之为上升子序列.如果不等号都是严格成立的,则称之为严格上升子序列.同理,如果前面不等关系全部取相反方向,则称之为下降子序列和严格下降子序列. 

长度最长的上升子序列称为最长上升子序列.本问题对于给定的整数序列,请求出其最长严格上升子序列的长度

输入描述 Input Description

第一行，一个整数N。

第二行 ，N个整数（N < = 5000）

输出描述 Output Description

输出K的极大值，即最长严格上升子序列的长度

样例输入 Sample Input

5

9 3 6 2 7

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

【样例解释】

最长严格上升子序列为3,6,7

【说明】

此题非常基础，希望每个人都能拿到此题的全部分数

题解：

#include <iostream>using namespace std;int dp[5555] = {0};int n;int a[5555];int k = 0;int maxV = 0;int main(){cin >> n;    for(int i=1; i<=n; i++) cin>>a[i];    dp[1] = 1;    for(int i=2; i<=n; i++)    {      maxV = 0;      for(int j=1; j<i; j++)      {        if(maxV<dp[j] && a[j]<a[i]) maxV = dp[j];      }      dp[i] = maxV + 1;      if(k<dp[i]) k = dp[i];    }    cout << k;return 0;}