POJ 2533 Longest Ordered Subsequence-白红宇

POJ 2533 Longest Ordered Subsequence

阅读量：5284 次

发布时间：2019-06-14

本文共 1005 字，大约阅读时间需要 3 分钟。

题目链接：

题意

求最大递增子序列的长度

思路

两种方法
1. dp[i] = max(dp[j]+1) 1<=j<=i-1(n^2)
2. LIS(nlogn)

代码

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int N = 1009;int dp[N], a[N];int main(){ int n; cin>>n; for(int i=0; i
             
              >a[i]; int ans = 0; for(int i=0; i

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int N = 1009;int dp[N], a[N];int binary_search(int len, int x){ int start = 0; while(start < len) { int mid = (start + len)/2; if(dp[mid] == x) return mid; else if(dp[mid] > x) len = mid; else start = mid+1; } return len;}int main(){ int n; cin>>n; for(int i=0; i
             
              >a[i]; int len = 1; dp[0] = -1; for(int i=0; i