NOIP2013 提高组花匠题解

发表于 2022-07-13 分类于信奥，题解阅读次数：

原题链接：Link

题目描述

思路

70分DP

看了各路大佬的题解，才知道原来有贪心的方法。让我这个写线段树的深深感受到了自己的弱小。。。

一开始就觉得这是一道DP题。考虑了两种状态定义方式:

\(dp[i][0]\) 表示以第 \(i\) 盆花为截止，最后两盆花呈上升趋势时的最长序列长度; \(dp[i][1]\) 表示以第 \(i\) 盆花为截止，最后两盆花呈下降趋势时的最长序列长度。
\(dp[i][0]\) 表示在前 \(i\) 盆花中，最后两盆花呈上升趋势时的最长序列长度; \(dp[i][1]\) 表示前 \(i\) 盆花中，最后两盆花呈下降趋势时的最长序列长度。

很快想出来了第一种的状态转移方程：枚举 \(i\) 之前的每一盆花 \(j\) ，则：

1 2	if (a[i] > a[j]) dp[i][0] = max(dp[i][0], dp[j][1] + 1); if (a[i] < a[j]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);

这样就有70分。 ~~实际上有80~~ 但是我居然怎么都想不到第2种的转移方程，后来看来各位大佬的题解才知道的。附在下面：

if (a[i] > a[i - 1]) dp[i][0] = dp[i - 1][1] + 1;
else dp[i][0] = dp[i - 1][0];
if (a[i] < a[i - 1]) dp[i][1] = dp[i - 1][0] + 1;
else dp[i][1] = dp[i - 1][1];

这样就是 \(O(n)\) 的。但是本juruo想不到啊。。。

所以我换了一个方法：用线段树维护。

100分解法

看到原来的转移方程：

1 2	if (a[i] > a[j]) dp[i][0] = max(dp[i][0], dp[j][1] + 1); if (a[i] < a[j]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);

其中 if (a[i] > a[j]) 和 if (a[i] < a[j]) 告诉我们：\(dp[i][0]\) 是所有以比 \(a[i]\) 更高的花盆结尾的“1”类序列的长度的最大值+1; \(dp[i][1]\) 是所有以比 \(a[i]\) 更高的花盆结尾的“1”类序列的长度的最大值+1。

可能说的不太清楚。我们想象有一个数组 \(b\) ，用 \(b[i]\) 表示以高度为 \(i\) 的花盆结尾的最长长度。那么当我们遇到一个高度为 \(h\) 的花盆时，他的最长长度一定是 \(b[h...maxh]\) 的最大值再加一。那为了维护这个区间最大值，写一个支持单点修改，区间查询的线段树就好了。当然，因为有两种不同的模式，也需要两棵线段树。

AC代码

code

#include <cstdio>

#define ls(x) (x << 1)
#define rs(x) (ls(x) | 1)
#define max(a, b) (a < b ? b : a)
#define min(a, b) (a < b ? a : b)

const int maxn = 1e5 + 5, maxh = 1e6 + 5;

int n, h_max, h_min;
int a[maxn];
int tree1[maxh * 4], tree2[maxh * 4];

void update(int *tree, int now, int now_l, int now_r, int id, int x) {
	if (now_l == now_r) {
		tree[now] = max(tree[now], x);
		return;
	}
	int mid = (now_l + now_r) >> 1;
	if (id <= mid) update(tree, ls(now), now_l, mid, id, x);
	else update(tree, rs(now), mid + 1, now_r, id, x);
	tree[now] = max(tree[ls(now)], tree[rs(now)]);
}

int ask(int *tree, int now, int now_l, int now_r, int ask_l, int ask_r) {
	if (ask_l > ask_r) return 0;
	if (ask_l <= now_l && now_r <= ask_r) return tree[now];
	int mid = (now_l + now_r) >> 1, res = 0;
	if (mid >= ask_l) res = max(res, ask(tree, ls(now), now_l, mid, ask_l, ask_r)); 
	if (mid + 1 <= ask_r) res = max(res, ask(tree, rs(now), mid + 1, now_r, ask_l, ask_r));
	return res;
}

int main() {
	scanf("%d", &n);
	h_min = 2147483647;
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		h_max = max(h_max, a[i]);
		h_min = min(h_min, a[i]);
	}
	for (int i = 1; i <= n; i++) {
		int tmp1, tmp2;
		tmp1 = ask(tree2, 1, h_min, h_max, h_min, a[i] - 1);
		tmp2 = ask(tree1, 1, h_min, h_max, a[i] + 1, h_max);
		update(tree1, 1, h_min, h_max, a[i], tmp1 + 1);
		update(tree2, 1, h_min, h_max, a[i], tmp2 + 1);
	}
	printf("%d\n", max(tree1[1], tree2[1]));
	return 0;
}

可能数据比较水，跑得飞快：Link