Unmerge

题意翻译

~~人物设定~~： 令 $a$ 和 $b$ 分别是长度为 $n$ 和 $m$ 的两个数组，这 $n+m$ 个元素都互不相同。我们递归定义一个新的数组合并操作 $\operatorname{merge}(a,b)$，合并后的数组长度为 $n + m$ ： 如果其中一个数组为空，则合并结果为另一个数组。也就是说，$\operatorname{merge}(\varnothing,b)=b$ 和 $\operatorname{merge}(\varnothing,a)=a$。特别的，$\operatorname{merge}(\varnothing,\varnothing)=\varnothing$。 如果两个数组均为非空且 $a_1<b_1$，则 $\operatorname{merge}(a,b)=[a_1]+\operatorname{merge}([a_2,\dots ,a_n],b)$。也就是说，我们删除 $a$ 的第一个元素 $a_1$ ，合并剩余的数组，然后将 $a_1$ 添加到结果的开头。 如果两个数组均为非空且 $a_1> b_1$ ，则 $\operatorname{merge}(a,b)=[b_1]+ \operatorname{merge}(a,[b_2,\dots ,b_m])$。也就是说，我们删除 $b$ 的第一个元素 $b_1$，合并其余的数组，然后将 $b_1$ 添加到结果的开头。 这其实就是归并排序算法中的一部分，即如果对 $a$ 和 $b$ 进行排序，那么 $\operatorname{merge}(a,b)$ 也将有序。但是，对于这个问题，我们将考虑对非有序数组执行相同操作的过程。例如，如果 $a = [3,1]$ ，$b = [2,4]$，则 $\operatorname{merge}(a,b)=[2,3,1,4]$。 排列是由 $1$ 到 $n$ 的 $n$ 个不同整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但是$[1,2,2]$ 不是排列（$2$ 在数组中出现两次），$[1,3,4]$ 也不是排列排列（$n = 3$，但数组中有 $4$个）。 题意： 给定长度为 $2n$ 的排列 $p$ 。确定是否存在两个数组 $a$ 和 $b$ ，每个数组的长度都为 $n$ ，并且没有相等的元素，使得 $p = \operatorname{merge}(a,b)$。 输入： 第一行一个整数 $t$ $(1\le t \le 1000)$ - 表示有 $t$ 组数据。 对于每组测试数据： 第一行一个整数 $n$ $(1\le n \le 2000)$ 第二行是一个包含 $2n$ 个整数的排列 $p_1, p_2 , \dots , p_{2n}$ 数据保证 $\sum n \le 2000$ 输出： 对于每组数据，若存在这两个数组 $a$ 和 $b$ ，则输出一行 `YES`，否则输出一行 `NO`。 样例解释： 在第一组数据中，$[2,3,1,4] = \operatorname{merge([3,1],[2,4])}$。 在第二组数据中，我们可以证明 $[3,1,2,4]$ 不能由两个长度为2的数组的合并。 在第三组数据中，$[3,2,6,1,5,7,8,4]$ = $\operatorname{merge}([3,2,8,4],[6,1,5,7])$。 在第四组数据中，$[1,2,3,4,5,6]$ = $\operatorname{merge}([1,3,6],[2,4,5])$。 translated by MicroMaker

题目描述

Let $ a $ and $ b $ be two arrays of lengths $ n $ and $ m $ , respectively, with no elements in common. We can define a new array $ \mathrm{merge}(a,b) $ of length $ n+m $ recursively as follows: - If one of the arrays is empty, the result is the other array. That is, $ \mathrm{merge}(\emptyset,b)=b $ and $ \mathrm{merge}(a,\emptyset)=a $ . In particular, $ \mathrm{merge}(\emptyset,\emptyset)=\emptyset $ . - If both arrays are non-empty, and $ a_1<b_1 $ , then $ \mathrm{merge}(a,b)=[a_1]+\mathrm{merge}([a_2,\ldots,a_n],b) $ . That is, we delete the first element $ a_1 $ of $ a $ , merge the remaining arrays, then add $ a_1 $ to the beginning of the result. - If both arrays are non-empty, and $ a_1>b_1 $ , then $ \mathrm{merge}(a,b)=[b_1]+\mathrm{merge}(a,[b_2,\ldots,b_m]) $ . That is, we delete the first element $ b_1 $ of $ b $ , merge the remaining arrays, then add $ b_1 $ to the beginning of the result. This algorithm has the nice property that if $ a $ and $ b $ are sorted, then $ \mathrm{merge}(a,b) $ will also be sorted. For example, it is used as a subroutine in merge-sort. For this problem, however, we will consider the same procedure acting on non-sorted arrays as well. For example, if $ a=[3,1] $ and $ b=[2,4] $ , then $ \mathrm{merge}(a,b)=[2,3,1,4] $ . A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array) and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). There is a permutation $ p $ of length $ 2n $ . Determine if there exist two arrays $ a $ and $ b $ , each of length $ n $ and with no elements in common, so that $ p=\mathrm{merge}(a,b) $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1\le t\le 1000 $ ) — the number of test cases. Next $ 2t $ lines contain descriptions of test cases. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 2000 $ ). The second line of each test case contains $ 2n $ integers $ p_1,\ldots,p_{2n} $ ( $ 1\le p_i\le 2n $ ). It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2000 $ .

输出格式

For each test case, output "YES" if there exist arrays $ a $ , $ b $ , each of length $ n $ and with no common elements, so that $ p=\mathrm{merge}(a,b) $ . Otherwise, output "NO".

输入输出样例

输入样例 #1

6
2
2 3 1 4
2
3 1 2 4
4
3 2 6 1 5 7 8 4
3
1 2 3 4 5 6
4
6 1 3 7 4 5 8 2
6
4 3 2 5 1 11 9 12 8 6 10 7

输出样例 #1

YES
NO
YES
YES
NO
NO

说明

In the first test case, $ [2,3,1,4]=\mathrm{merge}([3,1],[2,4]) $ . In the second test case, we can show that $ [3,1,2,4] $ is not the merge of two arrays of length $ 2 $ . In the third test case, $ [3,2,6,1,5,7,8,4]=\mathrm{merge}([3,2,8,4],[6,1,5,7]) $ . In the fourth test case, $ [1,2,3,4,5,6]=\mathrm{merge}([1,3,6],[2,4,5]) $ , for example.