ACM模版

描述

题解

给定 $n$ 个值为 $0$ 的数，下标从 $1 \sim n$，然后给了 $q$ 次区域加操作，选取这 $q$ 次操作的任意操作子集，可以得到一个最大的值，取所有操作后最大值在 $1 \sim n$ 的操作子集，他们的最大值组成了结果，这个结果是所有可能构成的在 $1 \sim n$ 之间最大值的数目。

样例 $1$，只选取第一次操作可以获得最大值为 $1$，只取第二次操作可以获得最大值 $2$，只取第三次操作可以获得最大值 $4$，取前两次操作可以获得最大值 $3$，所以在 $1 \sim n$ 之间，有 $1, 2, 3, 4$ 这 $4$ 种可以通过某种操作子集操作后构成。

这里我们可以用 $dp$，设置 $dp[i]$ 表示构成最大值 $i$ 时它所在的最靠右的位置，也就是右区间截止的位置。当我们输入 $l, r, x$ 时，我们可以枚举 $j = n - x \sim 0$ 的情况，这样可以保证构成的最大值在 $1 \sim n$ 之间。对于 $j != 0$ 的情况，考虑 $dp[j] >= l$，如果为真说明现在这个操作和之前的操作存在交集，所以可以叠加在一起，构成 $j + x$，反之则不能，对于 $j = 0$ 的情况，直接赋值 $dp[x] = r$ 即可。

这里有一点需要强调的，那就是必须将区间加操作排序，按照操作右区间从小到大排序即可。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e4 + 5;

struct Q
{
    int l, r, x;
    bool operator < (const Q &rhs) const
    {
        return r < rhs.r;
    }
} qs[MAXN];

int n, q;
int dp[MAXN];

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

    for (int i = 0; i < q; i++)
    {
        scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].x);
    }
    sort(qs, qs + q);

    for (int i = 0; i < q; i++)
    {
        int l = qs[i].l, r = qs[i].r, x = qs[i].x;
        for (int j = n - x; j >= 1; j--)
        {
            if (dp[j] >= l)
            {
                dp[j + x] = max(dp[j + x], dp[j]);
            }
        }
        dp[x] = r;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt += (dp[i] > 0);
    }

    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++)
    {
        if (dp[i] > 0)
        {
            printf("%d ", i);
        }
    }
    puts("");

    return 0;
}