[kuangbin带你飞]专题十二基础DP1 N - Longest Ordered Subsequence POJ - 2533(最长上升子序列LIS）...

快来打我* 2023-08-17 15:41 81阅读 0赞

# N - Longest Ordered Subsequence POJ - 2533 #

题目链接：[https://vjudge.net/contest/68966\#problem/N][https_vjudge.net_contest_68966_problem_N]

题目：

最长有序子序列如果a1 <a2 <... <aN，则排序ai的数字序列。 让给定数字序列（a1，a2，...，aN）的子序列为任何序列（ai1，ai2，...，aiK），其中1 <= i1 <i2 <... <iK <= N 例如，序列（1,7,3,5,9,4,8）具有有序的子序列，例如。 g。，（1,7），（3,4,8）和许多其他人。 所有最长有序的子序列长度为4，e。 g。，（1,3,5,8）。  
  
     当给定数字序列时，您的程序必须找到其最长有序子序列的长度。  
输入  
     输入文件的第一行包含序列N的长度。第二行包含序列的元素 - N个整数，范围从0到10000，每个用空格分隔。 1 <= N <= 1000  
产量  
     输出文件必须包含一个整数 - 给定序列的最长有序子序列的长度。  
样本输入  
  
    7  
     1 7 3 5 9 4 8  
  
样本输出  
  
    4

**思路：LIS问题，一定要注意dp\[i\]初始值为1；**

//
    // Created by hanyu on 2019/8/8.
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int maxn=1000+7;
    #define MAX 0x3f3f3f3f
    int main()
    {
        int T;
        while(~scanf("%d",&T))
        {
            int dp[maxn],a[maxn];
            memset(dp,0, sizeof(dp));
            for(int i=0;i<T;i++)
            {
                scanf("%d",&a[i]);
            }
            for(int i=0;i<T;i++)
            {
                dp[i]=1;
                for(int j=0;j<=i;j++)
                {
                    if(a[j]<a[i])
                        dp[i]=max(dp[i],dp[j]+1);
                }
            }
            int maxx=-1;
            for(int i=0;i<T;i++)
            {
                maxx=max(maxx,dp[i]);
            }
            printf("%d\n",maxx);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11324300.html

[https_vjudge.net_contest_68966_problem_N]: https://vjudge.net/contest/68966#problem/N