YBTOJ:划分数列

题目大意

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

题目分析

先预处理出两个数组lwi与hgi,lwi表示以i为结尾的单调不升子序列的起点,hgi表示以i为结尾的单调不降子序列的起点。
设d[i]为A1到Ai的最少划分数;
可得递推关系式:
\(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;
}
上一篇:比赛:2021-08-09:A


下一篇:ECNU 2977 成绩排序