这也算是我在hexo博客上面写的第一篇博客~
开始研究一些“有后效性的”DP
『题目』
(自己大概翻译了一下) 有n个木板,木板的高度为1~n的排列,你需要把它们排成“漂亮的栅栏”,即满足
或
(也就是一高一低)。
将所有方案按木板排列高度的字典序排列,求出第C个方案(保证存在)。
$0 < N\leq 20, C > 0$
T组数据($T\leq 100$)。
『解析』
这道题有一个重要的性质——栅栏的高度具体是多少对能否构成方案并不重要,起主要影响的是它们的相对高度。又因为高度是一个排列(没有重复),所以我们只要知道有多少个木板,我们就可以获得它们的相对高度!
而两种漂亮的栅栏我们可以把它抽象成:①”M”型,第一个栅栏比第二个栅栏矮;②”W”型,第一个栅栏比第二个栅栏高;
根据这两点,可以写出状态定义:
$dp[i][j][0/1]表示将 表示将 i$ 个木板排成一个漂亮的栅栏,且开头是其中第 j 高的木板的 W型/M型 方案总数。
状态转移方程式则是:
我们将第 $j$ 高的栅栏放在第一个,那么剩下 $i-1$ 个栅栏,因为第 $j$ 个栅栏被拿走,所以 $j$ 之后的所有栅栏都会往前挪一位,形成新的相对高度关系。此时若要构成W型,就要在新的相对高度中选择第 1~j-1 高的栅栏,若要构成M型,就要在新的高度中选择第 j~i-1 高的栅栏(新的相对高度的第 $j$ 高相当于原来相对高度关系的第 $j+1$ 高)。
上面是初始化。接下来我们需要确定方案——逐位确定。先枚举 $i$,表示现在正在求方案中第 i 个栅栏的高度,然后从小到大(因为字典序)枚举高度 $j$ ,如果 $j$ 还没有用过,尝试放入 $j$:
设求得的方案为 ans[];j 在还没有用过的栅栏中是第 k 高;
当 i=1 时,则可能是 W型也可能是 M型,所以方案数为 $dp[n][j][0]+dp[n][j][1]$;
当 i=2 时,则 j 的选择就确定了 M型或W型,所以判断 j 和 ans[1] 的大小关系,如果 j > ans[1] 则为W型,方案数为 dp[n-1][j][0];
当 $i > 2$ 时,M型或W型就确定了,所以我们根据 $ans[i-2]$ 和 $ans[i-1]$ 的大小关系就可以确定 $j$ 和 $ans[i-1]$ 的大小关系,要么是 $ans[i-2] < ans[i-1] > j$(M型) 要么是 $ans[i-2] > ans[i-1] < j$(N型)。当 $j$ 满足上述条件时,根据 M或N 型,它对应的方案数为 $dp[n-i+1][k][0/1]$;
如果 j 可以放入(也就是满足上面的条件),那么我们统计一下方案总数为 $tmp$,如果 $tmp\leq C$,那么 j 就是第 i 位的答案。
一直这样计算直到确定完所有位为止~具体见代码。
『源代码』
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问