【UOJ #246】【UER #7】套路

http://uoj.ac/contest/35/problem/246

神奇！我这辈子是想不出这样的算法了。

对区间长度分类讨论：题解很好的~

我已经弱到爆了，看完题解后还想了一晚上。

题解中“利用\(r_y\)进行计算更新答案”的具体方法是记录以当前点为右端点，任意两个数的差值的最小值大于等于j的区间的左端点，记为\(pos_j\)。

就这个问题我想了一晚上啊TWT，我不滚粗谁滚粗QAQ

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 200003;

int in() {

	int k = 0; char c = getchar();

	for (; c < '0' || c > '9'; c = getchar());

	for (; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - 48;

	return k;

}

int S, n, m, k, a[N], ans = 0, f[N], up, last[N], pos[N];

void solve_1() {

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

		f[i] = abs(a[i + 1] - a[i]);

		if (k <= 2) ans = max(ans, f[i]);

	}

	for (int p = 3; p <= S; ++p)

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

			f[i] = min(abs(a[i + p - 1] - a[i]), min(f[i], f[i + 1]));

			if (k <= p) ans = max(ans, f[i] * (p - 1));

		}

}

void solve_2() {

	int lo, bi;

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

		pos[0] = max(pos[0], last[a[i]]);

		for (int j = 1; j <= up; ++j) {

			pos[j] = max(pos[j], pos[j - 1]);

			lo = a[i] - j;

			bi = a[i] + j;

			if (lo >= 1) pos[j] = max(pos[j], last[lo]);

			if (bi <= m) pos[j] = max(pos[j], last[bi]);

			if (i - pos[j - 1] >= k)

				ans = max(ans, j * (i - (pos[j - 1] + 1)));

		}

		last[a[i]] = i;

	}

}

int main() {

	n = in(); m = in(); k = in();

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

		a[i] = in();

	S = ceil(sqrt(n));

	solve_1();

	up = m / S;

	solve_2();

	printf("%d\n", ans);

	return 0;

}

巴特西

【UOJ #246】【UER #7】套路

最新文章

热门文章