最长上升子序列

一个数的序列 a i ，当 a 1 < a 2 < # < a N 时，称这个序列是上升的。对于给定的一个序列 （ a 1 , a 2 ,# , a N ），可以得到一些上升子序列（ a i1 , a i 2 ,# , a iK ），这里 1 ≤ i1 < i 2 < # < iK ≤ N 。

例如，对于序列（1, 7, 3, 5, 9, 4, 8），它包含一些上升子序列，如（1, 7），（3, 4, 8）等。 这些子序列中最长的长度是 4，比如子序列（1, 3, 5, 8）。 你的任务是，对于给定的数字序列，求出最长上升子序列的长度。

2．输入描述

输入数据的第一行是序列的长度 N（1 ≤ N ≤ 1000 ）。第二行包含序列的元素（N 个 整数，每个元素的大小是从 0 到 10 000），中间用空格分开。

3．输出描述

输出必须包含一个整数（这个整数是给定序列的最长上升子序列的长度）。 本问题包含多个测试案例！ 输入数据的第一行是一个整数 N，然后是一行空行，后边是 N 个输入块。每个输入块 的格式在问题描述中已说明了。每个输入块之间有一空行。 输出格式包含 N 个输出块。输出块之间要有一行空行。

4．输入样例

1

7 1 7 3 5 9 4 8

5．输出样例

4

本题是一道经典的动态规划题目。

用动态规划解题，首先要把原问题分解为若干个子问题，这一点与递归方法类似。动 态规划与递归的区别在于：单纯的递归往往会导致子问题被重复计算，而运用动态规划方 法，子问题的解一旦被求出就会被保存，所以，每个子问题只需求解一次。

本题是要求最长上升子序列，如何把这个问题分解为子问题呢？经过分析，发现“求 以 a（k = 1,2,3,# , N）为终点的最长上升子序列的长度”是个比较好的子问题（这里把一个 k 上升子序列中最右边的那个数称为该子序列的终点）。 a k 是测试案例中的每一个元素。只 要把这 N 个子问题解决了，那么这 N 个子问题的解中，最大的那个就是整个问题的解。

上述子问题只与一个变量相关，即数字的位置。因此序列中数字的位置 k 就是状态， 而状态 k 对应的值，就是以 a k 作为终点的最长上升子序列的长度。这个问题的状态一共有 N 个。状态定义出来后，状态转移方程就比较好写出来了。假定 MaxLen(k ) 表示以 a k 作为 终点的最长上升子序列的长度，那么状态转移方程为： ? MaxLen(1) = 1 ? ? MaxLen(k ) = Max{MaxLen(i ) :1 ≤ i < k且a i < a k 且k ≠ 1} + 1

再有一点需注意的是，输出块之间有一空行，而不是每一块输出块后面跟一空行。

 1 #include<iostream>
 2 #include<string>
 3 #include<sstream>
 4 #include<set>
 5 #include<string.h>
 6 
 7 using namespace std;
 8 
 9 int main()
10 {
11     int t;
12     int ans[1005];
13     cin>>t;
14     while(t--)
15     {
16         memset(ans,0,sizeof(ans));
17         int n;
18         cin>>n;
19         int num[1005];
20         for(int i = 1; i <= n; i++)
21             cin>>num[i];
22         ans[1]=1;
23         for(int i = 2; i <= n; i++)
24         {
25             int maxx = 0;
26             for(int j = 1; j < i; j++)
27             {
28                 if(num[j]<num[i] && ans[j]>maxx)
29                 {
30                     maxx=ans[j];
31                 }
32             }
33             ans[i]=maxx+1;
34         }
35         int maxx=ans[1];
36         for(int i = 2; i <= n; i++)
37         {
38             if(ans[i]>maxx)
39                 maxx=ans[i];
40         }
41         cout<<maxx<<endl;
42         if(t)
43             cout<<endl;
44     }
45     return 0;
46 }

zoj 2136 Longest Ordered Subsequence