第十届蓝桥杯国赛G排列数（动态规划精简题解+图解）

动态规划

集合
$f[i][j]$ 表示填了前 $i$ 个数&＃xff0c;且填出来的排列为 “ $j$ 单调序列” 的方案数。&＃xff08;即含有 $j-1$ 个折点&＃xff09;

属性
数量

状态计算
将 $i$ 填到 $1\sim i-1$ 的一个排列中&＃xff0c;折点数量发生的变化。

需列举出$ i $插入到波峰和波谷、最左端点(0)、最右端点(i-1)、单调序列的情况。

下面画图列出&＃xff1a;&＃xff08;横线代表节点 $i$ 在 $1\sim i-1$ 序列中可插入的位置&＃xff0c;蓝线标记递减序列&＃xff0c;红线标记递增序列&＃xff09;
注&＃xff1a; 为了更方便直观的展示&＃xff0c;波峰和波谷中的节点不严格按大小绘图。

插入到单调序列中&＃xff0c;折点数量&＃43;2&＃xff0c;增加波峰和波谷各一个。

插入到波峰最高点的两端或波谷两端的最高点中&＃xff0c;折点数量不变。

插入到波谷最低点两端中&＃xff0c;折点数量&＃43;2。插入到波峰两端的最低点中涉及重复情况&＃xff0c;不作绘图。

插入到最左端点(0)&＃xff0c;折点数量&＃43;1。最右端点(i-1) 同理。

因此&＃xff0c;至多会多出两个折点。则状态转移方程应为&＃xff1a;
$f[i][j]\&＃61;f[i-1][j]\ast x\&＃43;f[i-1][j-1]\ast y\&＃43;f[i-1][j-2]\ast z$

下面求x,y,z.
显而易见&＃xff0c;

$x\&＃61;j$&＃xff0c;即 放入 $i$ 后&＃xff0c;放入i后&＃xff0c;使排列折点不增加的数量&＃xff0c;就是 原排列中折点数量&＃43;1。
$y\&＃61;2$&＃xff0c;即 放入 $i$ 后&＃xff0c;使排列中折点数量增加1的数量 &＃61; 2

根据上面的结论&＃xff0c;我们知道将 $i$ 放入这个序列后&＃xff0c;有 $j-2$ 种放置方式使该排列折点数不变&＃xff0c;有 2 种放置方式使该排列中折点数加一。
而将 $i$ 放入这 $i-1$ 个数中&＃xff0c;总共有 $i$ 种放法。

所以放入之后使其折点数量&＃43;2 的放法有 $i-(j-2)-2\&＃61;i-j$ 种。
故 $z\&＃61;(i-j)$。

转移方程&＃xff1a;
$f[i][j]\&＃61;f[i-1][j]\ast j\&＃43;f[i-1][j-1]\ast 2\&＃43;f[i-1][j-2]\ast (i-j)$

部分文字参考了 &＃64;垫底抽风 的题解。

C&＃43;&＃43; 代码

#include using namespace std;const int N &＃61; 520;
const int mod &＃61; 123456;int n, k;
int f[N][N];int main() //动态规划
{cin >> n >> k;f[1][1] &＃61; 1;f[2][1] &＃61; 2;for (int i &＃61; 3; i <&＃61; n; i&＃43;&＃43;)for (int j &＃61; 1; j <&＃61; k && j <&＃61; i; j&＃43;&＃43;){(f[i][j] &＃43;&＃61; f[i - 1][j] * j) %&＃61; mod;(f[i][j] &＃43;&＃61; f[i - 1][j - 1] * 2) %&＃61; mod;if (j > 1) (f[i][j] &＃43;&＃61; f[i - 1][j - 2] * (i - j)) %&＃61; mod;}cout << f[n][k];return 0;
}