Longest Ordered Subsequence
Time Limit:2000MSMemory Limit:65536K
Total Submissions:37623Accepted:16541
Description
A numeric sequence ofaiis ordered ifa1<a2< … <aN. Let the subsequence of the given numeric sequence (a1,a2, …,aN) be any sequence (ai1,ai2, …,aiK), where 1 <=i1<i2< … <iK<=N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).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
71 7 3 5 9 4 8
Sample Output
4
题意：给出一个序列 在其中找出这样一个子序列 除了第一项之外 子序列的每一项都比前一项要大 找出最长的一个上升子序列
题解：把问题分解 分解成序列中每一项最为终点的最大上升子序列 从第二项开始依次判断 最后找出最大的一项就是答案 状态转移方程为
nMaxLen (1) = 1
nMaxLen (k) = Max { MaxLen (i)：1<i < k 且 ai < ak且 k≠1 } + 1
下面给出简单代码实现：
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 1011;int an[maxn];int dp[maxn];int main(){int n;scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%d", &an[i]);}dp[1] = 1;for(int i = 2; i <= n; ++i){int cnt = 0;for(int j= 1; j < i; ++j){if(an[i] > an[j]){if(cnt < dp[j]){cnt = dp[j];}}}dp[i] = cnt +1;}int ans = 0;for(int i = 1; i <= n; ++i){ans = max(ans, dp[i]);}printf("%d\n", ans);return 0;}
，也有伤心的，既有令人兴奋的，也有令人灰心的，
