poj 2762 半连通图判断
poj 3076 dancing links 解n*n的数独

nlogn的最长不下降子序列

scturtle posted @ 2011年4月17日 00:58 in algorithm , 2161 阅读

做做dp,记下来,开始真是连dp都没想出来,由于数字只有1和2(poj 3671),写了个分治居然过了
搜了搜写O(n^2)的LIS果断超了,只好找资料,才知道只求长度的话有nlogn的LIS:
  使用d[j]来记录 长度为j的不减序列的最后一个元素 的值中的最小值,k为d数组的长度,初始可以为1,随着从前往后扫描输入数组a慢慢增长:
    1.若a[i]>=d[k],可以扩展了,d[++k]=a[i]

    2.若a[i]<d[1],则d[1]=a[i]

    3.否则,二分(易证明d为不减序列)找到d[1...k]中最大的j使d[j]<=a[i],因为d[j+1]>=d[j]>=a[i],所以更新d[j+1]=a[i]

最后k就是LIS的长度了

ref:这篇吴豪大牛的这篇


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter