题目大意

给定一个长度为\(n\)的数列A，要求划分最少的段数，使得每一段要么单调不降，要么单调不升。

题目分析

先预处理出两个数组lw_i与hg_i，lw_i表示以i为结尾的单调不升子序列的起点，hg_i表示以i为结尾的单调不降子序列的起点。
设d[i]为A₁到A_i的最少划分数；
可得递推关系式：
\(d[i]=min(d[lw[i]-1],d[hg[i]-1]])+1\)

Code

#include<iostream>
#include<cstdio>
#define sco 100010
using namespace std;
int d[sco],a[sco],hg[sco],lw[sco],n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	hg[1]=lw[1]=1;d[0]=d[1]=0;
	for(int i=2;i<=n;++i){
		if(a[i]<=a[i-1])
			lw[i]=lw[i-1];
		else lw[i]=i;
		if(a[i]>=a[i-1])
			hg[i]=hg[i-1];
		else hg[i]=i;
	}
	for(int i=1;i<=n;++i)d[i]=min(d[lw[i]-1]+1,d[hg[i]-1]+1);
	printf("%d",d[n]);
	return 0;
}