Deion
Redraiment是个聪明人，总是以奇怪的思考方法思考问题，但不知道为什么，他的解答总是最最巧妙，我们隆重地称他为诡异人！
有一天Jesse不经意中发现，诡异人的走路方法很特别，于是特别关注了他的走路规则。他发现诡异人总是往高处走，但走的步数总是最多，不知道为什么？你能替Jesse研究研究他最多走的步数吗？
发现了你也会是个聪明人
Input
输入数据包含一些测试用例，每个测试用例分为两行，第一行为整数n(0 < n ≤10000)，接下来一行是n个整数h（0≤ h ≤ 99），代表每点的高度值。
Sample Input
5
1 2 3 4 5
6
2 5 1 5 4 5
Sample Output
5
3
最长上升子序列问题是各类信息学竞赛中的常见题型，也常常用来做介绍动态规划算法的引例
算法渐近运行时间增量为(n^2)
问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列（设为s1,s2,...sn），使得这个子序列满足这样的性质，s1<s2<s3<...<sn并且这个子序列的长度最长。输出这个最长的长度。（为了简化该类问题，我们将诸如最长下降子序列及最长不上升子序列等问题都看成同一个问题，其实仔细思考就会发现，这其实只是<符号定义上的问题，并不影响问题的实质）
例如有一个序列:1 7 3 5 9 4 8,它的最长上升子序列就是 1 3 4 8 长度为4.
算法1(n^2):我们依次遍历整个序列，每一次求出从第一个数到当前这个数的最长上升子序列，直至遍历到最后一个数字为止，然后再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度，那么dp[i]=max(dp[j])+1,(j∈[1, i-1]); 显然dp[1]=1,我们从i=2开始遍历后面的元素即可。
模板为：
-
-
- template<class T>
- int LIS(T a[],int n)
- {
- int i,j;
- int ans=1;
- int m=0;
- int *dp=new int[n+1];
- dp[1]=1;
- for(i=2;i<=n;i++)
- {
- m=0;
- for(j=1;j<i;j++)
- {
- if(dp[j]>m&&a[j]<a[i])
- m=dp[j];
- }
- dp[i]=m+1;
- if(dp[i]>ans)
- ans=dp[i];
- }
- return ans;
- }
code:
- ＃i nclude "stdio.h"
- int num[10000+5];
- int dp[10000+5];
- int LIS (int n) {
- int i,j,ans = 1;
- dp[1] = 1;
- for (i = 2;i <= n;i++) {
- int m = 0;
- for (j = 1;j < i;j++) {
- if (dp[j] > m && num[i] > num[j]) {
- m = dp[j];
- }
- dp[i] = m + 1;
- if (dp[i] > ans) {
- ans = dp[i];
- }
- }
- }
- return ans;
- }
- int main () {
-
- int n;
- while (scanf ("%d",&n) != EOF) {
- int i,ans;
- for (i = 1;i <= n;i++) {
- scanf ("%d",num+i);
- }
- ans = LIS (n);
- printf ("%d\n",ans);
- }
- return 0;
- }
