在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。
对于一个 1∼n 的排列，如果可以将这个排列中包含 t 个折点，则它称为一个 t+1 单调序列。
例如，排列 (1,4,2,3) 是一个 3 单调序列，其中 4 和 2 都是折点。
给定 n 和 k请问 1∼n 的所有排列中有多少个 k 单调队列？
输入格式
输入一行包含两个整数 n,k。
输出格式
输出一个整数，表示答案。
答案可能很大，你可需要输出满足条件的排列数量除以 123456 的余数即可。
数据范围
1≤k≤n≤500
输入样例：
4 2
输出样例：
12
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 520;
const int mod = 123456;
int n, k;
int f[N][N];
int main() //动态规划
{
cin >> n >> k;
f[1][1] = 1;
f[2][1] = 2;
for (int i = 3; i <= n; i++)
for (int j = 1; j <= k && j <= i; j ++)
{
(f[i][j] += f[i - 1][j] * j) %= mod;
(f[i][j] += f[i - 1][j - 1] * 2) %= mod;
if (j > 1) (f[i][j] += f[i - 1][j - 2] * (i - j)) %= mod;
}
cout << f[n][k] << endl;
return 0;
}
这里先定义几个名词：
在一个排列中，一个山峰是指排列中的一个元素同时大于两边的元素。
在一个排列中，一个山谷是指排列中的一个元素同时小于两边的元素。
那么题目中的折点数量即为排列中山谷数量和山峰数量的和。
算法
(DP) O(nk)
考虑从 1 到 n 填整个排列。
记 f[i][j] 表示填了前i 个数，且填出来的排列为 “j 单调序列” 的方案数。
接下来考虑状态转移。
因为我们是从 1 到 n 逐个填的，所以我们只需考虑从 i−1 转移到 i 的情况即可，这大大降低了我们考虑的范围。
即使如此，这个状态转移依然比较难想，要先注意到下面这个性质：
将 i 填到 1∼i−1 的一个排列中，至多会多出两个折点（折点定义见题目描述）
这个性质不难理解，可以拿张纸随便画画。严格证明 其实一点都不严格 如下：
证明：
因为我们是将 i 填到 1∼i−1 的一个排列中，那么新填进去的 i 必然是排列中最大的数。
那么因为是最大的数，放到排列中之后，如果不放到最左/最右端，则必然成为一个山峰。
因为我们要放完之后的折点数量更多，所以我们假设不将其放到最左/最右端。
我们可以分以下三种情况分类讨论：
如果我们填到原排列中某个山峰的旁边：
假设我们放到了某个下标为 x 的山峰的左边，那么对于 xx 来说，它就不比它左边更大了，也就不再是山峰了。
对于 ii 的左边，因为原来它的右边是山峰，所以它必然比它右边小，放入 ii 之后它依然比右边小，所以它原来是啥现在就是啥。
而新放进去的 ii 则会成为一个山峰，那么我们相当于少了一个山峰后，又多了一个山峰，所以总的折点数量不变。
放到山峰右边同理。
如果我们填到原序列中的山谷的旁边：
假设我们放到了某个下标为 xx 的山谷的左边，那么对于 xx 来说，它依然是一个山谷。
对于新放进去的 ii 来说，它会成为一个山峰。
对于 ii 的左边来说，原来它的右边是山谷，所以必然比它小，而放入 ii 之后，它的右边就会比它大。
那我们就需要对它的左边考虑两种情况：
它的左边比它大
放入 ii 后，它的左边和右边都比自己大，则它会成为一个山谷。
它的左边比它小
放入 ii 后，它左边比自己小，右边比自己大，则它既不是山谷也不是山峰。
那么我们最多就会增加一个山峰和一个山谷，所以总的折点数量最多增加 22
放到山谷右边同理。
其它情况：
对于其它情况，假设我们放到排列中的 i 下标为 x，放入 i 后的排列为 p。假设 p[x−1]<p[x+1]。
放入 i 之后，考虑其左边的 p[x−1]，不论是否放入 i ，它右边都比自己大，所以放入 i 不对其构成影响。
考虑其右边的 p[x+1]，放入 i 后，它的左边比自己大了，那么我们需要对它右边考虑两种情况：
它的右边比它大
放入 i 后，它的左边和右边都比自己大，则它会成为一个山谷。
它的右边比它小
放入 i 后，它的左边比自己大，右边比自己小，则它既不是山峰也不是山谷。
那么我们最多会增加一个山峰和一个山谷，所以总的折点数量最多增加 2
综上所述，总的折点数量最多增加 2。
那么有了这个性质之后，可推出状态转移方程的“轮廓”大致如下：
f[i][j] = f[i - 1][j] * x + f[i - 1][j - 1] * y + f[i - 1][j - 2] * z
那么接下来的问题，就是解决 x,y,z 分别是什么。
首先算 xx，这里先直接给出结论：当 i>2 时，x=j，即 放入i后，使排列折点不增加的数量放入i后，使排列折点不增加的数量，就是 原排列中折点数量+1原排列中折点数量+1。
证明：
考虑如何放置 i，使折点数量不增加。
上面的证明过程中讨论过，如果我们将 ii 放到了原来某个山峰的旁边，则折点数量不增加。
但是，我们讨论的情况中，没有涉及到将 ii 放到边界的情况。
假设我们将 i 放到了排列的最左端，设原排列中最左端的元素为 xx。
因为 i 放到了排列最左端，所以 i 并不会成为山峰。
如果 x 右边的元素比 x 小，则放入i 后，x 既不是山峰也不是山谷，那么排列中总的折点数量就不会改变。
如果 x 右边的元素比 x 大，则放入 i 后，x 会成为一个山谷，那么排列中总的折点数量会增加 11。
那么如果将 i 放入最左端后，原排列中最左端两个元素递减，则排列中总的折点数量就不会改变。
同样，如果放入最右端，原排列中最右端两个元素递增，则排列中总的折点数量就不会改变。
那么就有 x=原排列中山峰个数×2+[原排列最左端两个元素递减]+[原排列最右端两个元素递增]
（那个 ×2 是因为我们可以将 i 放入山峰的左边，也可以放入其右边）
而我们的山峰和山谷必然是交错分布的，所以山峰个数和山谷个数的差必然不超过 1。
如果原排列中，山峰数量=山谷数量−1，则第一个折点和最后一个折点就都是山谷，那么最左端两个元素必然递减，最右端两个元素递增。（这里如果理解不了，可以画个柱状图）
那么就有 原排列中山峰个数×2+[原排列最左端两个元素递减]+[原排列最右端两个元素递增]=(山峰个数)+(山谷数量−1)+1+1=折点数量+1
如果 山峰数量=山谷数量，则要么是第一个折点是山峰、最后一个折点山谷，要么是第一个折点是山谷，最后一个折点是山峰，那么 [原排列最左端两个元素递减] 和 [原排列最右端两个元素递增] 必然一个为真一个为假。
那么就有 原排列中山峰个数×2+[原排列最左端两个元素递减]+[原排列最右端两个元素递增]=山峰个数+山谷数量+1=折点数量+1
如果 山峰数量=山谷数量+1，则第一个折点和最后一个折点就都是山峰，那么最左端两个元素必然递增，最右端两个元素递减。
那么就有 原排列中山峰个数×2+[原排列最左端两个元素递减]+[原排列最右端两个元素递增]=山峰个数+(山谷数量+1)+0折点数量+1
综上所述，放入i后，使排列折点不增加的数量=原排列中折点数量+1放入i后，使排列折点不增加的数量=原排列中折点数量+1，即 x=j
然后算 y，这里同样直接给出结论：当 i>2 时，y=2
证明：
根据上面性质中的证明过程，并没有发现有放完 i 之后折点数量增加 1 的情况。
所以想要放入 i 后，折点数量增加 1，必然是放在端点附近。
假设我们将 i 放入原排列左端点附近。
那么如果原排列最左端两个元素递减，则将 i 放到第一个元素后面时，排列中折点数量会增加 1。
如果原排列最左端两个元素递增，则将 i 放到第一个元素前时，排列中折点数量会增加 1。
所以不论什么情况，必然存在一种将 i 放到左端点的旁边的方案，使得排列中折点数量增加1。
右端点同理。
所以 i>2 时，放入放入i后，使排列中折点数量增加后，使排列中折点数量增加1的数量=2
最后，计算 z。
这个相对好算一些，考虑我们放入 i 之前，排列中共有 i−1个数，且该排列为 j−2 单调序列。
那么根据上面的一顿分析，我们知道将 i 放入这个序列后，有 j−2 种放置方式使该排列折点数不变，有 2 中放置方式使该排列中折点数加一。
而将 i 放入这 i−1 个数中，总共有 i 种放法。
所以放入之后使其折点数量 +2 的放法有 i−(j−2)−2=i−j 种。
故 z=(i−j)
那么我们就可以得到转移方程了：
f[i][j] = f[i - 1][j] * j + f[i - 1][j - 1] * 2 + f[i - 1][j - 2] * (i - j)
最后考虑初始化。
我们上面求得的 x,y,z，是有一定限制的，即 i>2，所以我们需要将 i=1 和 i=2 的情况都初始化出来。
对于 i=1 的情况，排列中不可能有折点，故排列必然为 1 单调序列，排列只有一种 f[1][1]=1。
对于 i=2 的情况，排列中不可能有折点，故排列必然为 1 单调序列，排列有两种 f[2][1]=2
终于写完了
时间复杂度
DP时间复杂度 = 转移复杂度 × 状态数量
本题中转移复杂度为 O(1)，状态数量为 n×k，故时间复杂度为 O(nk)
