题解：AT_arc104_c [ARC104C] Fair Elevator

GGapa · 2024-12-11 10:01:25 · 题解

[ARC104C] Fair Elevator

https://www.luogu.com.cn/problem/AT_arc104_c

感觉很好想也很好写的 DP 做法，实现方法不太一样。

先把无解的判掉，定义 F(i) 为，考虑前 i 层，最少需要用到多少个 (-1, -1) 使得能够填完，如果 F(2n) \le cnt，则合法，反之亦然，其中 cnt 为输入中有多少个 (-1, -1)。

借个图，如果一个区间能够合法，其一定如下图所示：

那么对于一个区间我们判断它要用多少个 (-1, -1) 就只需要扫一遍看一看有没有符合要求的对即可，转移是背包的转移，代码中为了方便使用了 set，时间复杂度为 O(n ^ 3 \log n)，似乎可以做到 O(n ^ 3)。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
using LL = long long;
using VI = vector<int>;

constexpr int INF = 1e9;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    set<pair<int, int>> s;

    int cnt = 0;
    for(int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;
        if(x > y && x != -1 && y != -1) return cout << "No" << '\n', 0;
        if(x == -1 && y == -1) {
            cnt++;
            continue;
        }
        if(s.count({x, y})) return cout << "No" << '\n', 0;
        s.insert({x, y});
    }

    auto check = [&](int r, int j) {
        int l = r - (j + 1) * 2 + 1;

        int ret = 0;
        rep(i, l, r - (j + 1)) 
            if(!s.count({-1, i + j + 1}) && !s.count({i, -1}) && !s.count({i, i + j + 1})) ret++;
        return ret;
    };

    vector<int> F(n * 2 + 1, INF);
    F[0] = 0;
    rep(i, 1, 2 * n) rep(j, 0, i) {
        if(i - (j + 1) * 2 < 0) break;
        F[i] = min(F[i], F[i - (j + 1) * 2] + check(i, j));
    }

    cout << (F[2 * n] <= cnt ? "Yes" : "No") << '\n';
    return 0;
}