【題解】Codeforces 1382D. Unmerge

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int t, n, a[4005], dp[2005];
vector <int> v;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n;
        memset(dp, 0, sizeof(dp));
        int pos = 0, cnt = 0;
        v.clear();
        for (int i = 0; i < n*2; i++){
            cin >> a[i];
            if (a[pos] >= a[i]) cnt++;
            else{
                v.push_back(cnt);
                cnt = 1;
                pos = i;
            }
        }
        v.push_back(cnt);
        dp[0] = 1;
        for (auto i:v){
            for (int j = n-i; j >= 0; j--){
                if (dp[j] == 1) dp[j+i] = 1;
            }
        }
        if (dp[n]) cout << "YES\n";
        else cout << "NO\n";
    }
}