自动搬运

查看原文

来自洛谷，原作者为

	flangeborg 是FL

搬运于2025-08-24 22:47:03，当前版本为作者最后更新于2023-08-03 14:50:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

修改题解太痛苦了，还是麻烦审核大大了。

一道特别痛苦的单调栈 + dp 的问题、500ms 的时间限制真的赛神仙。本人也用了挺长时间，也去参考了其他 AC 大佬的做法，最后才把这道题 A 过了。

题目大意

给定一个长度为 $n$ 的数组 $a$，一个合法序列的定义是：对于任意一个区间 $[l,r]$，区间的最小值为 $a_l$，最大值为 $a_r$。现在将这个长度为 $n$ 的数组 $a$ 分成 $k$ 段，使得其中每一段都是合法序列，试求 $k$ 最小值。

解题方法

• 看到“最小”、“最大”两个对于序列的限制，我们能够想到使用单调栈来维护数组。对于这道题我们需要用两个栈来维护。一个是严格单调递减的栈（$stk1[n]$），还有一个是单调递增的栈（$stk2[n]$）（关于为何使用这两种单调栈的问题建议配合后面的 AC 代码食用）。

• 其次，这道题还需要使用 dp 来求解。定义一个一维数组 $dp[n]$，对于任意一个数组下标 $i$，$dp_i$ 表示到 $i$ 坐标处，分割出来的序列全为合法序列的最小分割次数。

• 然后我们来构思状态转移方程，试想，如果当前坐标 $i$ 后（注意是 $i$ 坐标后，否则状态转移会出问题）需要进行分割以构成合法序列，上一次开始分割的坐标 $j$ 需要尽可能地小才能保证转移出的结果是最小的。

• 有了这样的想法，这时候就应该与前面提到的单调栈来配合了。由于这道题对数组内的顺序有严格要求，所以这道题使用单调栈的时候，栈中存储的不是数组变量的值，而是数组变量的下标。

两个重要的结论及其证明：

1. 在严格单调递减栈中，在当前循环到第 $i$ 次时，$i$ 入栈，由于栈中的严格递减性，栈顶 $i$ 所对应的 $a_i$ 一定会小于栈中 $i$ 下方（记为 $j$）所对应的 $a_j$ ，并且通过单调性也可以得出 $(j,i]$ 这个区间一定是合法的。

   证明：使用反证法，假设 $(j,i]$ 区间为非法，则会至少有一个坐标 $l$ 使得 $a_l > a_i$，则会使得当前递减栈除栈顶外第一个元素不是 $j$，出现矛盾，说明结论正确。

2. 在上一结论所描述的情况下，使用 STL 库中的 lower_bound 函数（意义及用法），以 $j$ 为目标（即作为函数中的第三个参数）在单调递增栈中二分查找到的结果（即一个小于等于 $j$ 的坐标，记为 $p$）在数组 $a$ 中所对应的值 $a_p$ 一定小于 $a_j$。

   证明：同样使用反证法，假设存在一个坐标 $p$ 使得 $a_p > a_j$，因为 $p < j$，所以当 $j$ 进入单调递增栈时，$p$ 会被弹出栈，出现矛盾，说明结论正确。

状态转移方程

• 通过这些结论以及先前的构思推导，我们终于可以把这道题目中最重要的状态转移方程给列出来了，代码如下：

  dp[i]=dp[lower_bound(stk2+1,stk2+top2+1,stk1[top1-1])-1]+1;

• 经过如此长的思维历程才推出来的状态转移方程竟然如此简单，接下来上代码。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[300005],dp[300005],top1,top2,stk1[300005],stk2[300005];
//stk1：严格单调递减栈 stk2：单调递增栈（使用手写栈的原因是时间过于紧张） 
int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
	for(int i = 1; i <= n; i++)
	{
		while(top1 && a[stk1[top1]] <= a[i]) top1--;
		stk1[++top1] = i;
		while(top2 && a[stk2[top2]] > a[i]) top2--;
		stk2[++top2] = i;
		//维护两个单调栈 
		dp[i] = dp[*lower_bound(stk2 + 1,stk2 + top2 + 1,stk1[top1 - 1]) - 1] + 1;
		//千辛万苦得出的状态转移方程 
	}
	printf("%d",dp[n]);
	return 0;
} 

代码就到这了，希望能够对大家有所帮助。