这里先定义几个名词:
在一个排列中,一个山峰是指排列中的一个元素同时大于两边的元素。
在一个排列中,一个山谷是指排列中的一个元素同时小于两边的元素。
那么题目中的折点数量即为排列中山谷数量和山峰数量的和。
算法
($\text{DP}$) $O(nk)$
考虑从 $1$ 到 $n$ 填整个排列。
记 $f[i][j]$ 表示填了前 $i$ 个数,且填出来的排列为 “$j$ 单调序列” 的方案数。
接下来考虑状态转移。
因为我们是从 $1$ 到 $n$ 逐个填的,所以我们只需考虑从 $i-1$ 转移到 $i$ 的情况即可,这大大降低了我们考虑的范围。
即使如此,这个状态转移依然比较难想,要先注意到下面这个性质:
将 $i$ 填到 $1 \sim i - 1$ 的一个排列中,至多会多出两个折点(折点定义见题目描述)
这个性质不难理解,可以拿张纸随便画画。严格证明 其实一点都不严格 如下:
证明:
因为我们是将 $i$ 填到 $1 \sim i - 1$ 的一个排列中,那么新填进去的 $i$ 必然是排列中最大的数。
那么因为是最大的数,放到排列中之后,如果不放到最左/最右端,则必然成为一个山峰。
因为我们要放完之后的折点数量更多,所以我们假设不将其放到最左/最右端。
我们可以分以下三种情况分类讨论:
- 如果我们填到原排列中某个山峰的旁边:
假设我们放到了某个下标为 $x$ 的山峰的左边,那么对于 $x$ 来说,它就不比它左边更大了,也就不再是山峰了。
对于 $i$ 的左边,因为原来它的右边是山峰,所以它必然比它右边小,放入 $i$ 之后它依然比右边小,所以它原来是啥现在就是啥。
而新放进去的 $i$ 则会成为一个山峰,那么我们相当于少了一个山峰后,又多了一个山峰,所以总的折点数量不变。
放到山峰右边同理。 - 如果我们填到原序列中的山谷的旁边:
假设我们放到了某个下标为 $x$ 的山谷的左边,那么对于 $x$ 来说,它依然是一个山谷。
对于新放进去的 $i$ 来说,它会成为一个山峰。
对于 $i$ 的左边来说,原来它的右边是山谷,所以必然比它小,而放入 $i$ 之后,它的右边就会比它大。
那我们就需要对它的左边考虑两种情况:- 它的左边比它大
放入 $i$ 后,它的左边和右边都比自己大,则它会成为一个山谷。 - 它的左边比它小
放入 $i$ 后,它左边比自己小,右边比自己大,则它既不是山谷也不是山峰。
那么我们最多就会增加一个山峰和一个山谷,所以总的折点数量最多增加 $2$
放到山谷右边同理。
- 它的左边比它大
- 其它情况:
对于其它情况,假设我们放到排列中的 $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$ 分别是什么。
首先算 $x$,这里先直接给出结论:当 $i > 2$ 时,$x = j$,即 $放入 i 后,使排列折点不增加的数量$,就是 $原排列中折点数量 + 1$。
证明:
考虑如何放置 $i$,使折点数量不增加。
上面的证明过程中讨论过,如果我们将 $i$ 放到了原来某个山峰的旁边,则折点数量不增加。
但是,我们讨论的情况中,没有涉及到将 $i$ 放到边界的情况。
假设我们将 $i$ 放到了排列的最左端,设原排列中最左端的元素为 $x$。
因为 $i$ 放到了排列最左端,所以 $i$ 并不会成为山峰。
如果 $x$ 右边的元素比 $x$ 小,则放入 $i$ 后,$x$ 既不是山峰也不是山谷,那么排列中总的折点数量就不会改变。
如果 $x$ 右边的元素比 $x$ 大,则放入 $i$ 后,$x$ 会成为一个山谷,那么排列中总的折点数量会增加 $1$。
那么如果将 $i$ 放入最左端后,原排列中最左端两个元素递减,则排列中总的折点数量就不会改变。
同样,如果放入最右端,原排列中最右端两个元素递增,则排列中总的折点数量就不会改变。
那么就有 $x = 原排列中山峰个数 \times 2 + [原排列最左端两个元素递减] + [原排列最右端两个元素递增]$
(那个 $\times 2$ 是因为我们可以将 $i$ 放入山峰的左边,也可以放入其右边)
而我们的山峰和山谷必然是交错分布的,所以山峰个数和山谷个数的差必然不超过 $1$。
如果原排列中,$山峰数量 = 山谷数量 - 1$,则第一个折点和最后一个折点就都是山谷,那么最左端两个元素必然递减,最右端两个元素递增。(这里如果理解不了,可以画个柱状图)
那么就有 $原排列中山峰个数 \times 2 + [原排列最左端两个元素递减] + [原排列最右端两个元素递增] = (山峰个数) + (山谷数量 - 1) + 1 + 1 = 折点数量 + 1$
如果 $山峰数量 = 山谷数量$,则要么是第一个折点是山峰、最后一个折点山谷,要么是第一个折点是山谷,最后一个折点是山峰,那么 $[原排列最左端两个元素递减]$ 和 $[原排列最右端两个元素递增]$ 必然一个为真一个为假。
那么就有 $原排列中山峰个数 \times 2 + [原排列最左端两个元素递减] + [原排列最右端两个元素递增] = 山峰个数 + 山谷数量 + 1 = 折点数量 + 1$
如果 $山峰数量 = 山谷数量 + 1$,则第一个折点和最后一个折点就都是山峰,那么最左端两个元素必然递增,最右端两个元素递减。
那么就有 $原排列中山峰个数 \times 2 + [原排列最左端两个元素递减] + [原排列最右端两个元素递增] = 山峰个数 + (山谷数量 + 1) + 0 + 0 = 折点数量 + 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$。
终于写完了
时间复杂度
$\text{DP}$ 时间复杂度 $=$ 转移复杂度 $\times$ 状态数量
本题中转移复杂度为 $O(1)$,状态数量为 $n \times k$,故时间复杂度为 $O(nk)$
C++ 代码
#include <cstdio>
const int N = 520;
const int mod = 123456;
int n, k;
int f[N][N];
int main()
{
scanf("%d%d", &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;
}
printf("%d\n", f[n][k]);
return 0;
}
$$ $$
j应该只能遍历到小于i吧
不过因为前面都是0的原因,计算出来也是0,没影响
tql!!!!
orz
tql!!
在证明“排列中折点数量增加 1的数量=2”时,“如果原排列最左端两个元素递增,则将 i 放到第一个元素前时,排列中折点数量会增加 1”的叙述部分需要细化,原因是:如果原排列最左端三个元素均递增,则将i放到第一个元素前或后共2个位置均会增加一个折点。
tql
为啥题解这么长,代码这么短啊,我不理解
为什么x+y+z!=i呢
这里我是通过其它状态来计算当前状态,
f[i - 1][j]
、f[i - 1][j - 1]
、f[i - 1][j - 2]
三个状态分别对应了三个不同的集合,所以并不能考虑 $i$ 在 $1 \sim i - 1$ 中的总放置方案数为 $i$。如果通过当前状态计算其它状态,即
f[i - 1][j]
分别向f[i][j]
、f[i][j + 1]
、f[i][j + 2]
转移,则三项系数之和应为 $i$。我觉得蓝桥杯这道题应该可以算压轴了hhh
太强啦
tql
### tql
分类讨论yyds
膜拜
牛