题目大意

给定 $N$ 个区间，编号 $1 \sim N$。这些区间有各自的价值与费用。其中，区间 $i$ 的左右端点坐标分别为 $l_i$、$r_i$，长度为 $r_i - l_i$，价值为 $v_i$，费用为 $w_i$。

现在，你要从这些区间中选出一些区间，使得它们的总长恰好为 $L$，并且两两之间没有重叠（重叠部分长度为 $0$）。

求最大总价值。

对于 $100\%$ 的测试数据，保证 $1 \le N \le 10000$，$1 ≤ L ≤ 1000$，$0 \le M \le 1000$，$0 \le l_i < r_i \le L$，$0 \le w_i \le 1000$，$0 \le v_i\le 1000000$。

思路

这道题的关键点在于数据范围。由于选择的区间要求不重叠且数据范围的 $l,r$ 在 $l$ 之内，那么如果有解必然覆盖整个数轴，也就是区间首尾相连。 最后对于有解的问题就转换成了删除不符合条件的问题。

之后能看出肯定是背包问题。我们去考虑怎么背包。首先，dp 要做的事就是寻找两个不同东西之间的联系。本题唯一的东西就是区间了，那我们想一想怎么去考虑这一点。

本题的关系就是 $dp[i]$ 了，但是我们发现光一个 $i$ 很明显是不够的，然后根据之前的结论，我们可以用现在覆盖的范围 $[0,j]$ 作为另外一个维度。这是因为我们总是需要看看重不重叠的。再然后，发现本题还有一个限制 $m$，那么再定义一维表示不超过 $k$ 的花费。

然后我们发现刚开始的 $i$ 就可以省略了。之后考虑转移。

那么我们记录一下每一个数结尾的地方。然后对于现在覆盖范围 $i$，从每一个以 $i$ 结尾的地方进行转移。设这个区间为 $k$，则从 $dp[i-k_l][j-k_v]$ 转移即可。

注意边界，为了方便将除了 $dp[0][0]$ 的其他位置都设成 $-1$ 即可。$dp[0][0]$ 是因为明显覆盖 $0$ 也花费 $0$ 的最大值为 $0$，其他的都可以从转移得来。

代码

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
typedef long long ll;
const ll MAXL = 1e3 + 5;
const ll MAXN = 1e4 + 5;
ll n, l, m, dp[MAXL][MAXL];
vector<ll> e[MAXL];
struct node {
    ll l, r, v, w;
} a[MAXN];

int main() {
    scanf("%lld%lld%lld", &n, &l, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld%lld%lld", &a[i].l, &a[i].r, &a[i].v, &a[i].w);
        e[a[i].r].push_back(i);
    }
    memset(dp, ~0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= l; ++i) {
        for (int j = m; j >= 0; --j) {
            for (int k = 0; k < e[i].size(); ++k) {
                ll num = e[i][k];
                if (j >= a[num].w) {
                    dp[i][j] = max(dp[i][j], dp[a[num].l][j - a[num].w] + a[num].v);
                }
            }
        }
    }
    ll ans = -1;
    for (int i = 0; i <= m; ++i) {
        ans = max(ans, dp[l][i]);
    }
    printf("%lld\n", ans);
    return 0;
}

总结

在之后的做题中，也要时刻关注数据范围所给的提示，不光是时间复杂度。以后做 dp 时我们定义时要做的就是从最基础的特征表示开始（如 $dp[i]$ 表示第 $i$ 个）持续添加必须要有区分度的维度。