跳至正文
题库4275
#4275

摆动序列

查看题目操作

摆动序列

题目描述

给定 k,统计满足以下条件的序列:

  1. 每个数均为 1 到 k 的整数。
  2. 序列至少含两个数。
  3. 序列中的数两两不同。
  4. 对第 3 项及以后:如果 ai−1 > ai−2,则 ai < ai−2;如果 ai−1 < ai−2,则 ai > ai−2。

条件比较的是新项与前两项中的较早一项 ai−2。例如 k=3 时,合法序列如下:

1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2

输入格式

一行一个整数 k,1 ≤ k ≤ 20。

输出格式

输出合法序列总数。

样例

3
8
1
0

来源

蓝桥杯 算法训练