2015合肥网络赛 HDU 5489 Removed Interval LIS+线段树(树状数组)

题意:

求序列中切掉连续的L长度后的最长上升序列

思路:

从前到后求一遍LIS,从后往前求一遍LDS,然后枚举切开的位置i,用线段树维护区间最大值,在i~n中找到第一个比a[i - L]大的位置k,用LIS[i - L] + LDS[k]更新答案.

代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#define eps 1e-8

#define INF 0x3f3f3f3f

#define LL long long

#define MAXN 500005

#define sqr(x) (x) * (x)

using namespace std;

int n, m, s;

int a[MAXN], b[MAXN], c[MAXN];

int f[MAXN], g[MAXN];

int LIS(int n){

	int i, k;

	k = 1;

	c[1] = b[n];

	g[n] = 1;

	for (i = n - 1; i >= 1; i--){

		if (b[i] > c[k]){

			c[++k] = b[i];

			g[i] = k;

		}

		else{

			int pos = lower_bound(c + 1, c + k + 1, b[i]) - c;

			c[pos] = b[i];

			g[i] = pos;

		}

	}

	return k;

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("in.txt", "r", stdin);

	freopen("out.txt", "w", stdout);

#endif // OPEN_FILE

	int T;

	scanf("%d", &T);

	int cas = 1;

	int n, L;

	while (T--){

		if (cas == 5){

			cas = 5;

		}

		scanf("%d%d", &n, &L);

		for (int i = 1; i <= n; i++){

			scanf("%d", &a[i]);

			b[i] = -a[i];

		}

		LIS(n);

		int ans = 0;

		int q = 0;

		memset(f, INF, sizeof(f));

		for (int i = L + 1; i <= n; i++){

			int p = lower_bound(f + 1, f + n + 1, a[i]) - f;

			ans = max(ans, p + g[i] - 1);

			p = lower_bound(f + 1, f + n + 1, a[i - L]) - f;

			f[p] = a[i - L];

			q = max(q, p);

		}

		ans = max(ans, q);

		printf("Case #%d: %d\n", cas++, ans);

	}

}

巴特西

2015合肥网络赛 HDU 5489 Removed Interval LIS+线段树(树状数组)

题意:

思路:

代码

最新文章

热门文章