本文迁移自洛谷原文。
结论+dp
我们可以先观察样例。当 $n=4$ 时，整个序列的最大值为8。在merge后的序列中8后面的数在原序列中一定跟在8后面。同理得，在7后面8前面的所有数都一定跟在7后面。
于是原序列被分成了很多小段。现在要做的事就是将这些小段重新组合，得到两个长度为 $n$ 的原序列。由于你已经分好了，所以你不需要知道小段内的内容，只要知道它们的长度，然后01背包即可。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
using namespace std;
const int mxn=4002;
vector<int>g[mxn];
int n,m;
int a[mxn],pos[mxn];
bool ban[mxn];
vector<int>v;
int dp[mxn][mxn];
inline void solve(){
cin>>n;for(int i=1;i<=n*2;++i)pos[i]=0;
for(int i=1;i<=n*2;++i)ban[i]=0;
v.clear();
for(int i=1;i<=n*2;++i)cin>>a[i],pos[a[i]]=i;
for(int i=n*2;i;--i){
int cnt=0;
for(int j=pos[i];j<=n*2 and !ban[j];)++cnt,ban[j]=1,++j;
if(cnt)v.push_back(cnt);
}
for(int i=0;i<=v.size();++i)for(int j=0;j<=n;++j)dp[i][j]=0;
dp[0][0]=1;
sort(v.begin(),v.end());
for(int i=0;i<v.size();++i){
for(int j=0;j<=n;++j){
if(dp[i][j]==1){
dp[i+1][j]=1;
if(j+v[i]<=n){
dp[i+1][j+v[i]]=1;
}
}
}
}
if(dp[(int)(v.size())][n])cout<<"YES\n";
else cout<<"NO\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;cin>>T;
for(;T--;)solve();
}
|