ACdream 1216 （ASC训练1） Beautiful People（DP）-白红宇

ACdream 1216 （ASC训练1） Beautiful People（DP）

阅读量：5812 次

发布时间：2019-06-18

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

题目地址：

pid=1216

这题一開始用的是线段树。后来发现查询的时候还须要DP处理。挺麻烦。。也就不了了之了。。后来想到，这题事实上就是一个二维的最长上升子序列。

。

要先排序，先按左边的数为第一keyword进行升序排序。再按右边的数为第二keyword进行降序排序。这种话，第一keyword同样的的肯定不在一个同一个上升子序列中。然后仅仅对第二keyword进行复杂度为O(n*logn)的DP，找出最长上升序列，然后处理前驱，并输出就可以。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;#define LL long longstruct node{ int x, y, num;}fei[110000];int cmp(node x, node y){ if(x.x==y.x) return x.y>y.y; return x.x
                
                 >1; if(a[mid]>=x) { high=mid-1; ans=mid; } else { low=mid+1; } } return ans;}int main(){ int n, i, j, pos, cnt; while(scanf("%d",&n)!=EOF) { for(i=0;i
                 
                  a[len]) { a[++len]=fei[i].y; pre[i]=d[len-1]; d[len]=i; } else { pos=bin_seach(fei[i].y); a[pos]=fei[i].y; pre[i]=d[pos-1]; d[pos]=i; } } printf("%d\n",len); cnt=0; /*for(i=0;i

转载地址：http://mlvbx.baihongyu.com/

你可能感兴趣的文章