•  
  • 数据结构和算法
  • 【POJ1887 || 2355 || 1631】Testing the CATCHER(最长递增(递减)子序列)NYOJ224

【POJ1887 || 2355 || 1631】Testing the CATCHER(最长递增(递减)子序列)NYOJ224

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 22 日

几个题目说的都挺很长,但是最后求的都是最长递减(递增)子序列。。。好吧 刷水题。。。

在O(n^2)的算法中:创建一个一维数组array[j],opt[],array[j]表示序列的元素,opt[i]表示以第i个元素结尾的序列中的最长下降子序列,初始化为1,对于一个opt[i],遍历前面的每个元素j,如果array[j]>array[i]且opt[j]>=opt[i],那么opt[j]就要加1,在这里,遍历前面的每个元素j,寻找此前最大的子序列时间复杂度为O(n),如果我们在一个有序的序列中查找此前最大的序列长度,我们就可以用二分查找,时间复杂度就会降为O(logn),总的时间复杂度就会为O(nlogn)。为此,我们增加一个一维数组B,B[i]表示当前序列为i的末尾元素的最小值。 例如对于序列:4 2 6 3 1 5 :

i 1 2 3 4 5 6
array 4 2 6 3 1 5
opt 1 1 2 2 1 3
B 1 3 5      

构建过程如下:

i=1时,opt[i]=1 B[i]=4(当前为1的序列的末尾元素的最小值)

opt 1 1 1 1 1 1
B 4          

i=2时,2不大于4,所以opt[i]=1,将B[1]更新为2

opt 1 1 1 1 1 1
B 2          

i=3时,6大于2,所以opt[i]=1+1,将B[2]更新为6

opt 1 1 2 1 1 1
B 2 6        

i=4时,3在2 6之间,所以opt[i]=1+1,将B[2]更新为3

opt 1 1 2 2 1 1
B 2 3        

i=5时,1小于2,所以opt[i]=1,将B[1]更新为1

opt 1 1 2 2 1 1
B 1 3        

i=6时,5大于3,所以opt[i]=2+1,将B[3]更新为5

opt 1 1 2 2 1 3
B 1 3 5      

opt[6]就是最后的结果。从构建的过程可以容易的证明一下两点:B是递增的。B是当前序列为i的末尾元素的最小值。以上“2不大于4”,“3在2 6之间”等等的判断采用二分查找,所以总的时间复杂度为:O(nlogn),核心的c代码如下:

for(i=1;i<=n;i++)
{
      num = array[i];
      left = 1;
      right = Blen;
      while(left<=right)
      {
          mid = (left+right)/2;
          if(B[mid]<num)
             left = mid+1;
          else
             right = mid-1;
      }
      opt[i] = left;
      B[left] = num;
      if(Blen<left)
          Blen = left;
     if(max<opt[i])
              max = opt[i];
}
printf("%d\n",max);

 

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
int arr[100010];  
int main(){  
    freopen("1.txt","r",stdin);  
    int n,j,i,num=1;  
    while(scanf("%d",&arr[0])!=EOF){  
        if(arr[0]==-1) break;  
        int count=0;  
        i=1;  
        while(scanf("%d",&arr[i])){if(arr[i]==-1) break;i++;}  
        n=i;  
        reverse(arr,arr+n);  
        for (i=0;i<n;i++){  
            j=lower_bound(arr, arr+count, arr[i])-arr;  
            arr[j]=arr[i];  
            if(j==count) count++;  
        }  
        printf("Test #%d:\n",num++);  
        printf("  maximum possible interceptions: %d\n\n",count);  
    }  
}  

这个是最长递增子序列

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
int arr[1002];  
int main(){  
    int n,j,i ;  
    while(scanf("%d",&n)!=EOF){  
        int count=0;  
        for (i=0;i<n;i++)  
            scanf("%d",&arr[i]);  
        for (i=0;i<n;i++){  
            j=lower_bound(arr, arr+count, arr[i])-arr;  
            arr[j]=arr[i];  
            if(j==count) count++;  
        }  
        printf("%d\n",count);  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日