#658(Div.2)D.Unmerge(블록+01 가방 문제)

제목 설명
Let a and b be two arrays of lengths n and m, respectively, with no elements in common. We can define a new array 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, merge(∅,b)=b and merge(a,∅)=a. In particular, merge(∅,∅)=∅. If both arrays are non-empty, and a1 If both arrays are non-empty, and a1>b1, then merge(a,b)=[b1]+merge(a,[b2,…,bm]). That is, we delete the first element b1 of b, merge the remaining arrays, then add b1 to the beginning of the result. This algorithm has the nice property that if a and b are sorted, then 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 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=merge(a,b).
Input
The first line contains a single integer t (1≤t≤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≤n≤2000). The second line of each test case contains 2n integers p1,…,p2n (1≤pi≤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.
Output
For each test case, output “YES” if there exist arrays a, b, each of length n and with no common elements, so that p=merge(a,b). Otherwise, output “NO”.
Example
Input 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 Output YES NO YES YES NO NO
Note
In the first test case, [2,3,1,4]=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]=merge([3,2,8,4],[6,1,5,7]). In the fourth test case, [1,2,3,4,5,6]=merge([1,3,6],[2,4,5]), for example.
제목의 대의.
두 개의 수조를 정의하는 합병 연산은 두 개의 수조 중 첫 번째 원소가 비교적 큰 것을 꺼낼 때마다 새 수조에 넣는 것이다. 현재 2*n의 길이를 가진 교환 수조를 제시한다. 두 개의 길이가 n인 교환 수조를 합친 후 원 수조로 만들 수 있느냐고 묻는다.
제목 분석
우리는 주어진 수조 a[]를 블록으로 나눌 수 있다. 예를 들어 [32 6 1 5 7 8 4]는 [32] [6 1 5] [7] [8 4] 네 조각으로 나눌 수 있다.분할 방법: 각 블록을 비교할 때 연속적으로 모두 수조에 넣을 수 있도록 하기 위해 우리는 블록을 나눌 때 첫 번째 수를 한 조각에 넣을 수 있다. 만약에 다음 수가 이 수보다 적으면 이 조각을 계속 넣고 어느 수가 첫 번째 수보다 많을 때까지 이 수는 새 블록의 첫 번째 수이다. 이렇게 추측한다.이런 방법으로 블록을 나눈 후에 이 문제는 하나의 가방 문제로 바뀌었다. m ， n， b[i]， ， 。01가방의 방법으로 마지막 f[n]가 n이 되는지 구하면 된다.
코드는 다음과 같다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define PII pair
using namespace std;
const int N=1e4+5;
int a[N],f[N];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		vector<int> b;
		int n;
		cin>>n;
		for(int i=1;i<=2*n;i++)
			cin>>a[i];
		
		int max=a[1],cnt=1;		//    ，max         ，cnt      
		for(int i=2;i<=2*n;i++)
		{
			if(max<a[i])
			{
				max=a[i];
				b.push_back(cnt);
				cnt=0;
			}
			cnt++;
		}
		memset(f,0,sizeof f);
		for(int i=0;i<b.size();i++)		//dp    
			for(int j=n;j>=b[i];j--)
				f[j]=std::max(f[j],f[j-b[i]]+b[i]);
		
		f[n]==n?puts("YES"):puts("NO");
	}
	return 0;
}