P1545 [USACO04DEC] Dividing the Path G 题解

Svemit · 2023-06-03 10:29:23 · 题解

更好的阅读体验

丢一发好理解又好写的线段树优化 dp。

题目传送门

简要题意

给定一个长为 l 的线段，求出尽量少的不相交区间覆盖整段线段，要求题目给的所有子区间只被 1 个区间覆盖。

分析

显然题目给的子区间 [s, e] 中只有 s 和 e 端点能作为线段端点，所以我们应该给 [s + 1, e - 1] 打上标记，这些不能作为线段端点。

令 dp_i 为覆盖 [0, i] 的最小的线段数量。

要求的就是 \min (dp_j) + 1, j \in [i - a \times 2, i - b \times 2]。

可以很轻易的写出一段暴力程序。

dp[0] = 0;
for(int i = 2; i <= l; i += 2) {
    if(flag[i]) continue;
    for(int k = a; k <= b; k ++) {
        int j = i - k * 2; // 在i, j 中间放一个线段
        if(j < 0) break;
        dp[i] = min(dp[i], dp[j] + 1);
    }
}

发现该算法的瓶颈会在枚举 k 的复杂度太高了，考虑优化掉。

区间最小值？线段树？

每次取出区间中的最小值算出 dp_i 递推下去就行。

代码就变成了这样：

    for(int i = a * 2; i <= l; i += 2) {
        if(flag[i]) continue;
        int ql = max(0, i - 2 * b), qr = i - 2 * a;
        dp[i] = query(ql, qr, 1) + 1;
        update(i, dp[i], 1);
    }

写一棵可爱的线段树就可以拉。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, l, a, b;
bool flag[N];
int c[N];
int dp[N];
struct segtree {
    int l, r, val;
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define val(x) tr[x].val
} tr[N << 2];
void pushup(int x) {
    val(x) = min(val(x << 1), val(x << 1 | 1));
}
void build(int l, int r, int x) {
    l(x) = l, r(x) = r, val(x) = INF;
    if(l == r) return;
    int mid = l + r >> 1;
    build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
}
void update(int pos, int v, int x) {
    if(l(x) == r(x)) {
        val(x) = v;
        return;
    }
    int mid = l(x) + r(x) >> 1;
    if(mid >= pos) update(pos, v, x << 1);
    else update(pos, v, x << 1 | 1);
    pushup(x);
}
int query(int l, int r, int x) {
    if(l <= l(x) && r(x) <= r) return val(x);
    int mid = l(x) + r(x) >> 1, res = INF;
    if(l <= mid) res = query(l, r, x << 1);
    if(r > mid) res = min(res ,query(l, r, x << 1 | 1));
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> l >> a >> b;
    for(int i = 1; i <= n; i ++) {
        int x, y;
        cin >> x >> y;
        c[x + 1] ++, c[y] --;
    }
    for(int i = 1; i <= l; i ++) {
        c[i] += c[i - 1];
        if(c[i] > 0) flag[i] = true;
    }
    build(0, l, 1);
    update(0, 0, 1);
    for(int i = a * 2; i <= l; i += 2) {
        if(flag[i]) continue;
        int ql = max(0, i - 2 * b), qr = i - 2 * a;
        dp[i] = query(ql, qr, 1) + 1;
        update(i, dp[i], 1);
    }
    if(dp[l] >= INF) dp[l] = -1;
    cout << dp[l] << '\n';
    return 0;
}

upd: 将写错的 [s + 1, e + 1] 改为 [s + 1, e - 1]，感谢 Aslf_Ek 指出错误。

upd: 在 Alisya 大佬的建议下将 flag 数组的处理改为差分处理，复杂度更稳定。