题解

Difficulty：4.1 / Easy

Tag：背包 DP

做题用时：21min。

Duel 到的，比对手早 0.1s 提交杀死比赛。

我：https://codeforces.com/contest/1381/submission/373298200
对手：https://codeforces.com/contest/1381/submission/373298205

---

好题啊。（喜）

注意到如果 $A_i\gt A_{i+1}$ 的话，那么两个数一定是同一侧数组的相邻元素。证明不难。

于是往这方面思考。

我们把这些递减的连成一条链，显然链头被弹出后面一连串的也会在同一个数组内被弹出。然后注意到有一些相邻的链头 $i,j$ 也会满足 $A_i\gt A_j$。此时如果这两个链在不同侧数组，也会产生矛盾。所以这两个应该也是同一侧数组的相邻链，可以直接连链。

注意到若干次连链后，所有剩余的链头满足 $A_i=\max_{j=1}^i A_j$，是单调递增的关系。而这些链头不管在哪一侧顺序都是正确的。

所以我们只需要选出若干个链，使得这些链的长度和为 $n$，将这些链排到一侧数组，剩下的排到另一侧数组即可。

这是一个可行性背包，可以 bitset 做到 $O(\frac{n^2}{w})$。

namespace cjdst{
    void solve(){
		int n;
		std::cin >> n;
		std::vector <int> a(n * 2 + 5);
		std::vector <int> b(n * 2 + 5);
		for(int i = 1; i <= n * 2; i++){
			std::cin >> a[i];
			b[i] = std::max(b[i - 1], a[i]);
		}
		std::vector <int> siz;
		int l = 1;
		for(int i = 1; i <= n * 2; i++){
			if(a[i] == b[i]){
				siz.push_back(i - l);
				l = i;
			}
		}
		if(l <= n * 2) siz.push_back(n * 2 - l + 1);
		std::bitset <2005> bits;
		bits.set(0);
		for(int i:siz){
			bits |= bits << i;
		}
		std::cout << (bits[n] ? "Yes\n" : "No\n");
	}
}

时间复杂度：$O(\frac{n^2}{w})$。