hdu1025（nlon(n)最长上升子序列）-白红宇

hdu1025（nlon(n)最长上升子序列）

阅读量：6897 次

发布时间：2019-06-27

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

题目链接：

大致思路：设置两个a,b数组，a数组存储数据，b数组存储最长不降序序列。此算法关键在于设计二分查找。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define LL long longusing namespace std;int dp[50500],a[50500];int solve(int n){ int len=1,low,high,mid; dp[1]=a[1]; for(int i=2;i<=n;i++) { low=1;high=len; while(low<=high) { mid=(low+high)/2; if(a[i]>dp[mid])low=mid+1; else high=mid-1; } dp[low]=a[i]; if(low>len)len=low; } return len;}int main(){ int n,x,y,cas=1; while(scanf("%d",&n)>0) { for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); a[x]=y; } int ans=solve(n); printf("Case %d:\n",cas++); if(ans==1) printf("My king, at most 1 road can be built.\n"); else printf("My king, at most %d roads can be built.\n",ans); printf("\n"); }}