[ACM_POJ_2533]Longest Ordered Subsequence

杰拉斯 | 时间：2012-04-03, Tue | 20,050 views
编程算法　

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

Source

POJ2533

思路：

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

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

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

示例：

I	0	1	2	3	4	5	6	7	8
Num[I]	1	4	7	2	5	8	3	6	9
F[I]	1	2	3	2	3	4	3	4	5

可得代码如下：

#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);
	return 0;
}

唔，一次性AC，吃湿炒牛河去 [龇牙] 。

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

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

老师的说法：

比较普遍的一个例子，动态规划可以看成一个二维数据，每个a[i][j] 由 a[i-1][*] 的取值来决定，一层一层的往上计算，每i层每一个元素近且只由第i-1层的元素计算而得。

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客