「CodeVS 1345」饥饿的奶牛 - 线性 DP

发表于 | 分类于

在 n（≤ 1000）条线段中选出若干条，保证任意两条线段没有公共点（端点也不能重合），使总长度最大。

链接

CodeVS 1345

题解

刚开始确实晕了，又是想线段树又是想背包 ……

保证线段不重合是个难点 …… 解决方法以线段的右端点排序，去除后效性。

以 表示前 i 条线段中选出若干条（必选第 i 条）的最大总长度，则转移方程为：

简单地说，就是只要保证最后一条线段不与当前线段重合，就可以添加当前线段。

注意最终答案是 ，而不一定是 ，因为不选最后一条线段可能比选最后一条线段更优。

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 1000;

struct Range {
    int l, r;

    int length() {
        return r - l + 1;
    }

    bool operator<(const Range &other) const {
        if (r == other.r) return l < other.l;
        else return r < other.r;
    }
} a[MAXN];

int n, f[MAXN];

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a[i].l, &a[i].r);
    }

    std::sort(a, a + n);

    int ans = 0;

    for (int i = 0; i < n; i++) {
        int max = 0;
        for (int j = 0; j < i; j++) {
            if (a[j].r < a[i].l) max = std::max(max, f[j]);
        }

        f[i] = a[i].length() + max;
        ans = std::max(ans, f[i]);
    }

    printf("%d\n", ans);

    return 0;
}