LIS(nlogn) POJ 3903 Stock Exchange

题目传送门

题意:LIS最长递增子序列  O(nlogn)

分析:设当前最长递增子序列为len,考虑元素a[i]; 若d[len]<a[i],则len++,并使d[len]=a[i]; 否则,在d[1~len]中二分查找第一个大于等于a[i]的位置j,使d[j]=a[i]。附上打印路径代码(准确性未知)

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std; const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[N], d[N], pos[N], fa[N];
int n; void LIS(void) {
int len = 1; d[1] = a[1]; fa[1] = -1;
for (int i=2; i<=n; ++i) {
if (d[len] < a[i]) {
d[++len] = a[i];
// pos[len] = i; fa[i] = pos[len-1];
}
else {
int j = lower_bound (d+1, d+1+len, a[i]) - d;
d[j] = a[i];
// pos[j] = i; fa[i] = (j == 1) ? -1 : pos[j-1];
}
}
printf ("%d\n", len);
// vector<int> res; int i;
// for (i=pos[len]; ~fa[i]; i=fa[i]) res.push_back (a[i]);
// res.push_back (a[i]);
// for (int i=res.size ()-1; i>=0; --i) printf ("%d%c", res[i], i == 0 ? '\n' : ' ');
} int main(void) {
while (scanf ("%d", &n) == 1) {
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
} LIS ();
} return 0;
}

  

上一篇:D3D9 effect (hlsl)(转)


下一篇:入木三分学网络第一篇--VRRP协议详解第一篇(转)