cf1382D---思维+01背包

题目链接：https://codeforces.com/contest/1382/problem/D

简单题意：给定1到2*n的一个排列，问是否能由两个长度为n的数组归并得到

首先注意到，原来2*n的排列中，一个数和右边连续的所有比它小的数，是必须在一个数组里的。这样就可以把原2*n排列分段。比如样例中 6 1 3|7 4 5|8 2各个段的长度就是3 3 2。如果有一些段的长度和为n，那么把它们放到一个数组里就可以了（然后将另外的段放到另一个数组，容易发现这样是满足的）。是否存在一些段长度和为n可以用01背包判断

#include<bits/stdc++.h>
using namespace std;

const int maxn=4000+10;
int t,n,i,j,k,cnt,a[maxn],c[maxn],dp[maxn];

int main(){
	scanf("%d",&t);
	while (t--){
	  scanf("%d",&n);
	  for (i=1;i<=2*n;i++) scanf("%d",&a[i]);
	  a[2*n+1]=1e9; i=1;j=2; cnt=0;
	  while (i<=2*n){ //* 求出每段长度 
	  	while (a[j]<a[i]) j++;
	  	c[++cnt]=j-i;
	  	i=j; j=i+1;
	  }
	  memset(dp,0,sizeof(dp)); dp[0]=1;
	  for (i=1;i<=cnt;i++) //01背包 
	    for (j=n;j>=c[i];j--)
	      if (dp[j-c[i]]) dp[j]=1;
	  if (dp[n]) puts("YES
"); else puts("NO
");
	}
	return 0;
}