[UVA]10534 - Wavio Sequence（LIS最长上升子序列） - c++编程基础

TOP

[UVA]10534 - Wavio Sequence（LIS最长上升子序列）

2015-07-20 17:44:41 来源: 作者: 【大中小】浏览:1次

Tags：UVA 10534 Wavio Sequence LIS 最长上升序列

这题一看10000的数据量就知道必须用nlog(n)的时间复杂度。

所以特意去看了最长上升子序列的nlog(n)的算法。

如果有2个位置，该位置上的元素为A[i]和A[j],并且他们满足以下条件:

1.dp[i] = dp[j] (dp[x]代表以x结尾的最长上升子序列长度)

2.A[i] < A[j]

3.i < j

那么毫无疑问，选择dp[i] 一定优于选择dp[j]

那么我们可以利用g[i]表示长度为i的序列的最后一个元素的最小值.

每次拿到一个A[i],在g[i]里面寻找到一个元素，使得g[t] >= A[i].

dp[i] = t;

之后更新最小值 g[t] = A[i];

求最大下降子序列的话返回来遍历一遍就行了。

之后 ans = max(ans, min(dp[i],dp[j]) * 2 - 1);

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                  
                    #include
                   
                     #include
                    
                      using namespace std; #define _PI acos(-1.0) typedef long long LL; typedef unsigned long long ULL; typedef pair
                     
                       pill; /*====================================== ======================================*/ #define MAXD 10010 #define INF (1 << 30) void LIS1(int dp[],int A[],int n){ int g[MAXD]; for(int i = 1 ; i <= n ; i++) g[i] = INF; for(int i = 1 ; i <= n ; i++){ int k = lower_bound(g + 1 , g + n + 1 , A[i]) - g; dp[i] = k; g[k] = A[i]; } return ; } void LIS2(int dp[],int A[],int n){ int g[MAXD]; for(int i = 1 ; i <= n ; i++) g[i] = INF; for(int i = n ; i >= 1 ; i--){ int k = lower_bound(g + 1 , g + n + 1 , A[i]) - g; dp[i] = k; g[k] = A[i]; } return ; } int main(){ int n; int A[MAXD]; while(scanf("%d",&n) != EOF){ for(int i = 1 ; i <= n ; i++) scanf("%d",&A[i]); int dp1[MAXD] , dp2[MAXD]; LIS1(dp1,A,n); LIS2(dp2,A,n); int ans = 0 ; for(int i = 1 ; i <= n ; i++){ int t = min(dp1[i],dp2[i]); ans = max(ans,2 * t - 1); } printf("%d\n",ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：icpc live archive6454(状压搜索)	下一篇：LA 6459 Infinite Go (模拟，搜索)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: