划分数列

题目地址

Solution

考虑递推。

设\(f_i\)表示\(a_1\sim a_i\)的最少划分段数，\(p_i\)代表以\(i\)结尾单调不降的一段的起点，\(q_i\)则表示以\(i\)结尾单调不升的一段的起点，注意：起点代表这一段第一个数的前一个坐标。

我们可以得到以下转移方程：

\[\large f_i=\min(f_{p_i}+1,f_{q_i}+1) \]

也就是说对于\(a_1\sim a_i\)的分段数可以是由上一个单调不降（升）的数段加上当前这一段（指\(a_{p_i+1}\ or\ a_{q_i+1}\sim a_i\)这一段）。

那如何求\(p_i\)和\(q_i\)呢？

显然分为两种情况：（以求\(p_i\)为例，\(q_i\)同理）

• \(a_i\ge a_{i-1}\)，那么\(p_i\)的起点与上一项相同，即\(p_i=p_{i-1}\)。
• \(a_i< a_{i-1}\)，那么\(p_i\)的起点更新，\(p_i=i-1\)。

时间复杂度为\(O(n)\)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int f[N],p[N],q[N],a[N];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		p[i]=q[i]=i-1;
		if(a[i]>=a[i-1])p[i]=p[i-1];
		if(a[i]<=a[i-1])q[i]=q[i-1];
		f[i]=min(f[p[i]]+1,f[q[i]]+1);
	}
	printf("%d",f[n]);
	return 0;
}