hdu1025 最大递增子序列 - c++编程基础

把题意转换一下就是最大递增子序列问题不过就是数的排列不是按输入顺序

500000果断用n*logN的时间复杂度

这个算法是把每个数一个个往里面插入然后一步步更新len（当前最大子序列）最后得出全局的最大子序列
num【i】表示数i出现的位置 dis【k】表示子序列长度为k的出现的最小的位置（比如x=dis【k】表示最先出现子序列为k的位置为x）
注意for循环跑到i表示以num【i】结尾的最大子序列

现在就出现两种情况
1》dis【len】 2》dis【len】》num【i】然后用二分查找到最小的j是dis【j】>num【i】；令dis【j】=num【i】注意讨论没有的情况

下面是详细代码

#include
   
    
#include
    
      #include
      
      using namespace std
      ; int dis
      [500010
      ],num
      [500010
      ]; int main() { int n
      ,i
      ,j
      ,a
      ,b
      ,d
      =1
      ; while(~scanf
      ("%d"
      ,&n
      )) { for(i
      =1
      ;i
      <=n
      ;i
      ++) { scanf
      ("%d%d"
      ,&a
      ,&b
      ); num
      [a
      ]=b
      ; } int len
      =1
      ; int L
      ,R
      ; dis
      [1
      ]=num
      [1
      ]; for(i
      =2
      ;i
      <=n
      ;i
      ++) { if(dis
      [len
      ]<num
      [i
      ]) { len
      ++; dis
      [len
      ]=num
      [i
      ]; } else if(dis
      [len
      ]>num
      [i
      ]) { L
      =1
      ; R
      =len
      ; int flash
      =0
      ; while(L
      <=R
      ) { int mid
      =(L
      +R
      )/2
      ; if(dis
      [mid
      ]<num
      [i
      ]) L
      =mid
      +1
      ; else if(dis
      [mid
      ]>num
      [i
      ])R
      =mid
      -1
      ; else {flash
      ==1
      ;break;} } if(!flash
      )dis
      [L
      ]=num
      [i
      ]; } } printf
      ("Case %d:\n"
      ,d
      ++); if(len
      ==1
      ) printf
      ("My king, at most 1 road can be built."
      ); else printf
      ("My king, at most %d roads can be built."
      ,len
      ); printf
      ("\n"
      ); printf
      ("\n"
      ); } return 0
      ; }