CF480D Parcels 题解

题意：

有 \(n\) 件包裹，每个包裹是一个盒子，都有它自身的质量和载重 (即它上方能承受的最大质量)。cxy 最近得到了一个新的包裹处理系统，这个系统以如下方式工作。初始时，有一个（可以堆放盒子的）平台，它的载重为 \(S\)，接下来，你能以如下的规则在平台上堆放盒子：

如果平台是空的，你可以将盒子堆放在平台上，否则，你只能在新的盒子放在最高的盒子上面。

任何时刻，（平台上）所有盒子的总质量不能超过 \(S\) （即平台的载重）。

对任意一个盒子，任何时刻，在它上面的所有盒子的总质量不能超过这个盒子的载重。

并且你只能取走当前位于最上面的盒子（即形成栈型结构）。

系统接收到了这 \(n\) 件包裹，已知第 \(i\) 个包裹在时刻 \(\text{in}_i\) 出现，它的质量和载重分别为 \(w_i,s_i\)，每个包裹都有它的价值，其中第 \(i\) 个包裹的价值为 \(v_i\)。然而，为了获得（赚得）这 \(v_i\) 的价值，这个系统要求它刚好在时刻 \(\text{out}_i\) 被出售，否则将无法获得任何价值。于是，cxy 可以选择跳过部分包裹（即不接收这些包裹），当然她也无法获得任何价值。

任何操作所花费的时间可以忽略不计，这意味着你可以在一个时刻做多件事情（比如取走若干包裹，在堆放若干包裹）。

注意一旦一个包裹被取走后，它就不会影响后续对包裹的操作。

由于这系统非常复杂，并且包裹数有很多，cxy 想要知道如果她合理利用这个系统，她最多能得到多少钱。

输入格式：

第一行包含两个非负整数 \(n,S(n≤500,S≤1000)\) ，表示包裹的个数和平台的载重。

接下来的 \(n\) 行，每行包含 \(5\) 个非负整数 \(\text{in}_i,\text{out}_i,w_i,s_i,v_i(0\le\text{in}_i<\text{out}_i<2n,~0 \le w_i,s_i\le 1000,~1\le v_i\le 10^6)\)，

保证不存在两个包裹的出现时间 (\(\text{in}_i\)) 和出售时间 (\(\text{out}_i\)) 均相同。

输出格式：

输出一行一个整数，表示 cxy 能得到的价值的最大值。

容易发现，时间有交集的两个包裹，如果他们不是包含关系，则一定只能二选一。

但如果是包含关系，这俩就都可以选。并且在一个大集合内，可以选若干个小的。

再加上这个栈的性质，很容易把它和树联系到一起。

我们把每个包裹按右端点排序，则若 \(v\) 是 \(u\) 的子节点，\(v\) 一定出现的比 \(u\) 早，这就方便dp了。

设 \(f_{i,j}\) 表示对于第 \(i\) 个包裹（节点），当前剩余的最大载重量为 \(j\) ，\(i\) 所在子树中的最大价值。

注意，由于原图可能是个森林，所以我们要加个虚拟节点（平台）把它们连起来。

考虑转移。设 \(g_b (\text{in}_i \le b \le \text{out}_i)\) 表示到时刻 \(b\) 位置的最大价值，则对于 \(i\) 的某个子节点 \(u\) ，当 \(b = \text{out}_u\) 时 \[ \large g_b \uparrow g_{\text{in}_u} + f_{u,\min \left\{j-w_i, s_i\right\}} \] 最后别忘了它自己， \(f_{i,j}=g_{\text{out}_i} + v_i\) 。最终答案就是虚拟点载重为 \(S\) 的答案。

时间复杂度 \(\mathcal{O}(n^3)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(555))
#define M ((int)(1e3 + 15))

struct node
{
    int i,o,w,s,v;
    void read() { cin >> i >> o >> w >> s >> v; }
    friend bool operator < (node a, node b) {
        return a.o == b.o ? (a.i > b.i) : (a.o < b.o);
    }
}p[N];
int n,S,f[N][M],g[M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> S; p[0] = {0, (n << 1 | 1), 0, S, 0};
    for(int i = 1; i <= n; i++) { p[i].read(); } sort(p, p + 1 + n);
    for(int i = 0; i <= n; i++)
        for(int j = p[i].w; j <= S; j++)
        {
            int b = p[i].i, nj = min(j - p[i].w, p[i].s); g[b] = 0;
            for(int k = 0; k < i; k++)
                if(p[i].i <= p[k].i)
                {
                    for(; b < p[k].o; b++) g[b + 1] = g[b];
                    up(g[b], g[p[k].i] + f[k][nj]);
                }
            f[i][j] = g[b] + p[i].v;
        }
    cout << f[n][S] << '\n';
    return 0;
}