Unmerge
题目出处
题目大意
给定整数 \(n\) 和一个长度为 \(2n\) 的一个排列（\(1 \sim 2n\) 都只出现一次），问是否存在两个长度为 \(n\) 的序列经过一次归并后可以成为给定的 \(2n\) 长度的排列。（注意：序列可以是无序的）
知识点、思路
DP、背包问题
具体想法、推导
要解决这个问题，需要注意到序列中不自然的情况。
因为归并的过程是从两个序列的起始位置选取更小的位置插入归并后的序列，因此一般情况下，在归并后的序列中，更小的数字应该出现在更大的数字前面。除非在一个序列里，大的数把小的数挡住了，导致大的数先被排进了归并后的序列里。
举个例子，比如说 \(1\ 2\ 4\ 3\ 2\ 1\) 这个归并后序列，可以发现从 \(4\) 开始序列开始递减，假设 \(3,2,1\) 不是在 \(4\) 同一个序列的后面，它们一定会在归并后的序列里排在 \(4\) 的前面，所以就证明了归并后连续的递减段在归并前一定属于同一个序列。
于是我们可以预处理出所有的递减段长度，然后通过01背包算法判断它们能否恰好填满一个长度为 \(n\) 的序列，若能填满，则剩下的递减序列可以填入另一个长度为 \(n\) 的序列，从而满足题目要求。
算法时间复杂度为\(O(n^2)\)
示例代码
void solve()
{
cin>>n;
for (int i=1;i<=2*n;i++) cin>>a[i];
int cnt=0; //递减段的数量
for (int i=1;i<=2*n;i++){
int j=i;
while (j<=2*n&&a[j]<=a[i]) j++;
j--;
b[++cnt]=j-i+1;
i=j;
}
for (int i=0;i<=n;i++) f[i]=-1e9;
f[0]=0;
for (int i=1;i<=cnt;i++){
for (int j=n;j>=b[i];j--)
f[j]=max(f[j],f[j-b[i]]+1);
}
if (f[n]>0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}