蓝桥杯算法训练VIP-摆动序列

题目

题目链接

题解

DFS。

这么暴力？没想到这都过了。

首先枚举前两个数，因为摆动序列最少俩数，枚举好前两个数之后就开始dfs。 每次递归都让答案加一，因为两种情况存在包含关系也属于两种不同的情况；判断第i-2个数与i-1个数的大小关系，根据大小关系确定第i个数的遍历范围，这样可以降低时间复杂度。 其他部分就是单纯的dfs。

代码

#include
using namespace std;

int n, a[30], vis[30], ans;

void dfs(int x) {
	if(x > n) return ; // 边界 
	
	ans ++;
//	for(int i = 1;i  i-2 
		for(int i = a[x-1]+1;i n;
	
	for(int i = 1;i