ARC068F Solitaire

根据套路这种计数类题我们应该考虑什么样的序列满足性质。

我们考虑我们是如何构造这段序列的。

一开始，我们将 $1\sim n$ 的排列放入双端队列中，那应该是这样的：

然后我们考虑取出后哪些数是可以放在 $1$ 前面的：

大概就应该是上图红色和蓝色的（当然分成两段的可能是红色而不是绿色）。

于是我们发现 $1$ 前面的序列（包括 $1$）可以划分为两个单调递减的子序列（$1$ 划给与他相邻的那个序列，反正他是最小的）：

我们发现如果是这样的话，与 $1$ 相邻颜色序列的末尾一定是$1$，另一个子序列的末尾（即最小值）一定比绿色序列中的最大值要大。

于是我们就可以愉快地 dp 辣！

显然后面那段绿色的我们是可以随便选的，即每次选左边和选右边都可以，也就是$2^{n-k-1}$。

我们考虑如何 dp 出前面的序列。

一个非常 simple 的想法是令 $f_{i,j,k}$ 表示到第 $i$ 位，红色序列（结尾为 $1$ 的序列，下同）的最小值为$j$，蓝色序列的最小值为$k$。如果我们加进去一个数字$x$，我们考虑加入哪一段序列。

我们有如下贪心：我们尽量把小的数扔给红色序列（因为蓝色序列的最小值越大越可能符合条件）。如果$x<j$，那我们就丢给红色序列，否则只能丢给蓝色序列。

但由于我们无法枚举 $x$，所以上面的dp 行不通，但我们得到了一个有趣的贪心策略。

有上面的贪心策略，我们发现只要我们能知道所有合法的 $x$，我们就不必关心$k$ 是多少。所以我们考虑令 $f_{i,j,k}$ 表示红色序列有 $i$ 个数，蓝色序列有 $j$ 个数，红色序列的最小值为 $k$ 的方案数。

我们考虑对于一个状态$f_{i,j,k}$，我们有两种方案进行转移：

1. 选择一个最大的数放入蓝色序列，当然前提条件是存在这个大于 $k$ 的数。由于这个数不可能放在红色序列里了，且如果不选最大的那个而去选其他大于 $k$ 的数，那也就意味着这个最大的数要给绿色序列。而这样一来绿色序列就会有一个数比蓝色序列大，这显然是不合法的。也就是$f_{i,j,k} \to f_{i,j+1,k}$。
2. 选择一个比 $k$ 小的数给红色序列。也就是$f_{i,j,k} \to f_{i+1,j,1\sim k-1}$

这样做复杂度$\mathcal{O}(n^4)$，前缀和优化一下复杂度就变成了$\mathcal{O}(n^3)$

我们发现我们并不必关心 $i$ 和$j$，因为根据上面的贪心策略，我们只要知道最小的一个（红色序列的最小值显然比蓝色的最小值小，因为比红色序列最小值小的数只会被放入红色序列）就可以转移了。

我们令 $f_{i,j}$ 表示到第 $i$ 位，最小的一位为$j$，我们发现转移方式和上面没有本质区别：

1. 选择一个最大的数放入蓝色序列。$f_{i,j}\to f_{i+1,j}$。
2. 选择一个比 $k$ 小的数给红色序列。$f_{i,j}\to f_{i+1,1\sim k-1}$。

发现第一维可以直接压掉，然后直接 dp 即可。