题意：

给定一个2n的排列p[]，问是否存在两个长为n的数组a和b，不断取出a数组首和b的数组首中最小的那一个，最终可以得到p

思路：

假设 \(p_i\) 为 p 中最大的元素，则 \(p_i,p_{i+1},\cdots p_{2n}\) 一定是 a 或 b 中连续的一段。把这些元素从p中取出，组成一个区间，由此可以得到cnt个区间，所有区间的首元素恰是p的最长上升子列。

然后看能否用这些区间的长度凑出n。这是个经典的 "子集和dp"，f[i][j] 表示能否用前 \(i\) 个元素恰好拼成 \(j\)。可以用used数组优化到 \(O(n\sqrt n)\) ，详见lyd蓝书多重背包的例题：硬币。

不优化的话 \(O(n^2)\) 也能过。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[4005], idx, maxx, cnt;
bool f[2005]; int used[2005], c[4005];
signed main()
{
    int T; cin >> T; while(T--)
    {
        scanf("%d", &n), m = n * 2;
        fill(a + 1, a + m + 1, 0);
        maxx = 0, cnt = 0;
        for(int i = 1; i <= m; i++)
        {
            int x; scanf("%d", &x);
            if(x < maxx) a[cnt]++;
            else a[++cnt]++, maxx = x;
        }

        idx = 0; fill(c + 1, c + 1 + m, 0);
        sort(a + 1, a + 1 + cnt);
        for(int i = 1; i <= n; i++)
        { //合并相等元素
            if(a[i] == a[i-1]) c[idx]++;
            else a[++idx] = a[i], c[idx]++;
        }

        fill(f, f + n + 1, 0); f[0] = 1;
        for(int i = 1; i <= idx; i++)
        {
            fill(used, used + n + 1, 0);
            for(int j = a[i]; j <= n; j++)
                if(!f[j] && f[j-a[i]] && used[j-a[i]] < c[i])
                    f[j] = 1, used[j] = used[j-a[i]] + 1;
        }

        puts(f[n] ? "YES" : "NO");
    }

    return 0;
}