首页 > 代码库 > zoj 2136 Longest Ordered Subsequence

zoj 2136 Longest Ordered Subsequence

最长上升子序列

一个数的序列 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