Difficulty：4.1 / Easy Tag：背包 DP 做题用时：21min。 Duel 到的，比对手早 0.1s 提交杀死比赛。 我：https://codeforces.com/contest/1381/submission/373298200 对手：https://codeforces.com/contest/1381/submission/373298205 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 好题啊。（喜） 注意到如果 Ai>Ai+1A_i\gt A_{i+1}Ai >Ai+1 的话，那么两个数一定是同一侧数组的相邻元素。证明不难。 于是往这方面思考。 我们把这些递减的连成一条链，显然链头被弹出后面一连串的也会在同一个数组内被弹出。然后注意到有一些相邻的链头 i,ji,ji,j 也会满足 Ai>AjA_i\gt A_jAi >Aj 。此时如果这两个链在不同侧数组，也会产生矛盾。所以这两个应该也是同一侧数组的相邻链，可以直接连链。 注意到若干次连链后，所有剩余的链头满足 Ai=max⁡j=1iAjA_i=\max_{j=1}^i A_jAi =maxj=1i Aj ，是单调递增的关系。而这些链头不管在哪一侧顺序都是正确的。 所以我们只需要选出若干个链，使得这些链的长度和为 nnn，将这些链排到一侧数组，剩下的排到另一侧数组即可。 这是一个可行性背包，可以 bitset 做到 O(n2w)O(\frac{n^2}{w})O(wn2 )。 时间复杂度：O(n2w)O(\frac{n^2}{w})O(wn2 )。