nlogn的最长不下降子序列
scturtle
posted @ 2011年4月17日 00:58
in algorithm
, 2976 阅读
做做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的长度了
2022年9月25日 12:40
Leading educational institutions and subject experts of the state provided sample guess paper with practice question bank in chapter wise important questions and answer solutions through newspapers and model sets, Bihar Board 10th Social Model Paper we have recommended to every student can download expert questions of Bihar Board 10th Model Paper 2023 for Social Science to practice regular mock test.Leading educational institutions and subject experts of the state provided sample guess paper with practice question bank in chapter wise important questions and answer solutions through newspapers and model sets.