【题解】AT_arc068_d [ARC068F] Solitaire

· · 个人记录

【题解】AT_arc068_d [ARC068F] Solitaire

感觉和别人不太一样的思考过程。

首先对于题目中的双端队列一定形如一个单谷的形态，要求我们第 k 位取到 1 ，那一定是在第 k 位时单谷的一侧取完了剩下了单谷的另一侧，接下来的 n-k 位相当于是在一个单调序列的两端随便取，最后一位除外，所以不管前面是什么，后面都是 2^{n-k-1} 中序列。

考虑对于前 k-1 位的限制，要求这个序列可以划分为两个单调递减的子序列，且其中一个子序列的最小值比未选数的最大值大。经典的一步，先来考虑如果我们有一个确定的序列如何判断是否满足上面的条件。

考虑这样一个贪心策略，从前往后考虑，如果当前元素接到第一个序列上是合法的就接到第一个序列，否则接到第二个序列上，不难发现这样一定是最优的，且可以保证的二个序列的最小元素最大，也就是尽可能满足上面的限制，考虑以这个贪心过程为基准去 dp ，为了判断是否能接到第一个序列上，我们要记录第一个序列的结尾元素，也就是整个序列当前的最小元素，设 f_{i,j} 表示填完了前 i 个元素当前第一个序列结尾元素为 j 的方案数，如果当前位填的元素 w 小于 j 直接转移即可，当 w>j 时我们要把它接到第二个序列上，此时我们发现这题的限制非常好啊，第二个序列的最小值必须比所有没选的数都大，所以我们我们此时 w 必须的等于当前序列中未出现的数的最大值，否则序列一定不合法，以为就是我们隐形的确定了 w 的取值，此时只要保证 w 存在即可。

这样直接 dp 就可以做到 n^2 了。