[ACM_POJ_2533]Longest Ordered Subsequence

Longest Ordered Subsequence

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 21942 Accepted: 9441

Description
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input
7
1 7 3 5 9 4 8

Sample Output
4

Source

POJ2533

思路：

这道题用穷举暴力破解的话是很不明智的，因为当n增加时，运算量将是几何倍数增长。动态规划的三要素是阶段、状态、决策，我们以此来进行分析（按照我当前刚学动态规划的理解）：

我们按照数字的编号划分阶段，那么以某个数字为结尾的最长子序列长度就是该阶段的状态，最优状态则是之前的最大子序列长度中的最大值，决策便是以当前数字为结尾的最长子序列长度 = 最优状态 + 1，我们用状态转移方程来表示：

a[n] = max({a[i] | 0 < i < n}) + 1

可得代码如下：

#include<stdio.h>
int main(){
	int n, ans = 1;
	scanf("%d", &n);
	int *num = new int[n];
	int *a = new int[n];
	for(int i = 0; i < n; ++i){
		scanf("%d", &num[i]);
		int max = 0;
		for(int j = 0; j < i; ++j){
			if(num[j] < num[i] && a[j] > max){
				max = a[j];
			}
		}
		a[i] = max + 1;
		if(a[i] > ans)
			ans = a[i];
	}
	printf("%d", ans);
}

唔，一次性AC 。

本题的引申——[ACM_ZOJ_1733]Longest Common Subsequence（最长公共子序列）

后记：问了老师，原来这种做法还不算是动态规划，只是具备了动态规划的思想。

老师的说法：

比较普遍的一个例子，
动态规划可以看成一个二维数据，

每个a[i][j] 由 a[i-1][*] 的取值来决定，
一层一层的往上计算，每i层每一个元素近且只由第i-1层的元素计算而得。

原文地址（本人博客）：http://lanfei.sinaapp.com/2012/04/464.html

欢迎访问交流。