洛谷3084 [USACO13OPEN]照片Photo

原题链接

神仙\(DP\)啊。。。

题解请移步隔壁大佬的博客\(QAQ\)

#include<cstdio>

using namespace std;

const int N = 2e5 + 10;

int L[N], R[N], q[N], f[N];

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

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

		p |= c == '-';

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

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline int minn(int x, int y)

{

	return x < y ? x : y;

}

inline int maxn(int x, int y)

{

	return x > y ? x : y;

}

int main()

{

	int i, j = 0, n, m, x, y, l = 1, r = 0;

	n = re();

	m = re();

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

		R[i] = i - 1;

	for (i = 1; i <= m; i++)

	{

		x = re();

		y = re();

		R[y] = minn(R[y], x - 1);

		L[y + 1] = maxn(L[y + 1], x);

	}

	for (i = n; i; i--)

		R[i] = minn(R[i], R[i + 1]);

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

		L[i] = maxn(L[i], L[i - 1]);

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

	{

		for (; j <= R[i]; j++)

			if (f[j] >= 0)

			{

				for (; l <= r && f[q[l]] < f[j]; r--);

				q[++r] = j;

			}

		for (; l <= r && q[l] < L[i]; l++);

		if (l <= r)

			f[i] = f[q[l]] + 1;

		else

			f[i] = -1;

	}

	printf("%d", f[n + 1] > 0 ? f[n + 1] - 1 : -1);

	return 0;

}

巴特西

洛谷3084 [USACO13OPEN]照片Photo

原题链接

最新文章

热门文章