专栏文章

题解：AT_arc104_c [ARC104C] Fair Elevator

GGGapa
AT_arc104_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqtipiy
此快照首次捕获于
2025/12/04 10:29
3 个月前
此快照最后确认于
2025/12/04 10:29
3 个月前
查看原文

[ARC104C] Fair Elevator

https://www.luogu.com.cn/problem/AT_arc104_c
感觉很好想也很好写的 DP 做法，实现方法不太一样。
先把无解的判掉，定义 F(i)F(i) 为，考虑前 ii 层，最少需要用到多少个 (−1,−1)(-1, -1) 使得能够填完，如果 F(2n)≤cntF(2n) \le cnt，则合法，反之亦然，其中 cntcnt 为输入中有多少个 (−1,−1)(-1, -1)。
借个图，如果一个区间能够合法，其一定如下图所示：
那么对于一个区间我们判断它要用多少个 (−1,−1)(-1, -1) 就只需要扫一遍看一看有没有符合要求的对即可，转移是背包的转移，代码中为了方便使用了 set，时间复杂度为 O(n3log⁡n)O(n ^ 3 \log n)，似乎可以做到 O(n3)O(n ^ 3)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...