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

题意

给出一个大小为 $2n$ 的排列，判断能否找到两个长为 $n$ 的子序列，使得二者归并排序后能够得到该排列。

题解

将原排列拆分为一个个连续子序列，每次从大于上一子序列首部的元素处分出下一连续子序列，只要将这些子序列按照拆分先后排列，归并排序后一定可以得到原排列。

之后即判断能否将这些子序列排列为两个长为 $n$ 的序列即可，可以用状压 $dp$，也可以用 $01$ 背包。

状态 $dp$：每次将之前的每一个可行长度加上当前长度得到新一批的可行长度，然后将当前长度标记为可行。

$01$ 背包：将每个子序列的长度视为其花费与价值，最后判断花费为 $n$ 的背包总价值是否为 $n$ 即可。

代码一

状压 $dp$：$O_{(\frac{n^2}{w})}$ （$w$ 视机器字长而定，参考资料）

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n; cin >> n;

    int mx = 0;

    vector<int> idx;

    for (int i = 0; i < 2 * n; ++i) {

        int x; cin >> x;

        if (x > mx) {

            mx = x;

            idx.push_back(i);

        }

    }

    idx.push_back(2 * n);

    vector<int> len;

    for (int i = 1; i < idx.size(); ++i) {

        len.push_back(idx[i] - idx[i - 1]);

    }

    bitset<2020> dp;

    for (auto i : len) {

        dp |= dp << i;

        dp[i] = 1;

    }

    cout << (dp[n] ? "YES" : "NO") << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

代码二

$01$ 背包：$O_{(vn)}$

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n; cin >> n;

    int mx = 0;

    vector<int> idx;

    for (int i = 0; i < 2 * n; ++i) {

        int x; cin >> x;

        if (x > mx) {

            mx = x;

            idx.push_back(i);

        }

    }

    idx.push_back(2 * n);

    int N = idx.size() - 1, p = 0;

    int cost[N] = {}, val[N] = {};

    for (int i = 1; i < idx.size(); ++i) {

        cost[p] = val[p] = idx[i] - idx[i - 1];

        ++p;

    }

    map<int, int> dp;

    for (int i = 0; i < N; ++i) {

        for (int j = n; j >= cost[i]; --j) {

            dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);

        }

    }

    cout << (dp[n] == n ? "YES" : "NO") << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

巴特西

Codeforces Round #658 (Div. 2) D. Unmerge（dp）

题意

题解

代码一

代码二

最新文章

热门文章