题解
2026-05-02 15:18:09
发布于:广东
22阅读
0回复
0点赞
Difficulty:4.1 / Easy
Tag:背包 DP
做题用时:21min。
Duel 到的,比对手早 0.1s 提交杀死比赛。
我:https://codeforces.com/contest/1381/submission/373298200
对手:https://codeforces.com/contest/1381/submission/373298205
好题啊。(喜)
注意到如果 的话,那么两个数一定是同一侧数组的相邻元素。证明不难。
于是往这方面思考。
我们把这些递减的连成一条链,显然链头被弹出后面一连串的也会在同一个数组内被弹出。然后注意到有一些相邻的链头 也会满足 。此时如果这两个链在不同侧数组,也会产生矛盾。所以这两个应该也是同一侧数组的相邻链,可以直接连链。
注意到若干次连链后,所有剩余的链头满足 ,是单调递增的关系。而这些链头不管在哪一侧顺序都是正确的。
所以我们只需要选出若干个链,使得这些链的长度和为 ,将这些链排到一侧数组,剩下的排到另一侧数组即可。
这是一个可行性背包,可以 bitset 做到 。
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");
}
}
时间复杂度:。
全部评论 2
你的 duel 账号是啥
1周前 来自 湖北
0aaaaaaaaaaaaabaaaaaaaaa
6天前 来自 广东
0
拜谢大手子
1周前 来自 广东
0








有帮助,赞一个