[数据结构与算法]1970 花匠

1970 花匠

这个题呢，和上回wyq老师出的题差不多，我用一次就AC了，这样的题目叫做波形动态规划题目
是用来解决类似于山峰的题目
首先，我们定义一个数组f[i][0/1]第一个维度表示位置，第二个维度表示上升或者下降
所以，对于每一个状态都有两个情况，前面是上升或者下降
啥意思
全网并没有解释清楚
我来！
【【【【
对于每一个点，他要么是一个转折点，要么就是持续点；换句话说，要么它前面都是递增的，要么它上面是递减的
所以
就分了四个情况来讨论

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZE=1e5+5;
int n;
int f[SIZE][2];
int temp;
int a[SIZE];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	f[1][0]=f[1][1]=1;//第一个维度表示位置，第二个维度表示上升或者下降 
	for(int i=2;i<=n;i++)
	{
		if(a[i]>a[i-1]) f[i][0]=f[i-1][1]+1; //如果递增，是转折点
		else f[i][0]=f[i-1][0];//如果递增，是上升点
		if(a[i]<a[i-1]) f[i][1]=f[i-1][0]+1;//如果递减，是转折点
		else f[i][1]=f[i-1][1];//如果递减，是下降点
	}
	cout<<max(f[n][1],f[n][0])<<endl;
	return 0;
 }