蓝桥杯算法训练VIP-摆动序列-题解（C++代码）

解题思路:直接DFS列举所有可能情况即可，并且当数列长度>=2时，总次数col+1

注意事项:注意题目说的两两不同  是指相邻两个数不相同

参考代码:

#include<iostream>

#include<cstdio>

using namespace std;

int a[22],col,n;

void dfs(int u){

if(u>=2) {

col++;

}

if(u>=n) return;

for(int i=1;i<=n;i++){

if(i==a[u-1]) continue;

if(u<=1){

a[u]=i;

dfs(u+1);

}

else{

if((a[u-1]>a[u-2]&&i<a[u-2])||(a[u-1]<a[u-2]&&i>a[u-2])){

a[u]=i;

dfs(u+1);

}

}

}

}

int main (){

scanf("%d",&n);

dfs(0);

cout<<col<<endl;

return 0;

}