1643

题意

给定若干条线段，问最多可以安排多少条使得没有重合。

思路

贪心，同安排schedule，按结束时间早的排序。

Code

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define maxn 1000010

using namespace std;

typedef long long LL;

int n;

struct Seg {

    int l, r;

    bool operator < (const Seg& s) const { return r < s.r; }

}seg[maxn];

void work() {

    for (int i = 0; i < n; ++i) {

        scanf("%d%d", &seg[i].l, &seg[i].r);

        if (seg[i].l > seg[i].r) swap(seg[i].l, seg[i].r);

    }

    sort(seg, seg+n);

    int r = -inf, cnt = 0;

    for (int i = 0; i < n; ++i) {

        if (seg[i].l >= r) ++cnt, r = seg[i].r;

    }

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

}

int main() {

    scanf("%d", &n); work();

    return 0;

}

3027

题意

给定若干条线段，每条线段都有各自的价值，问怎样安排使得不重叠且总价值最大。

思路

Code

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define maxn 1010

using namespace std;

typedef long long LL;

struct Seg {

    int l, r; LL w;

    bool operator < (const Seg& s) const { return r < s.r; }

}seg[maxn];

LL dp[maxn];

int main() {

    int n;

    scanf("%d", &n);

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

    sort(seg, seg+n);

    dp[0] = seg[0].w;

    LL ans = dp[0];

    for (int i = 1; i < n; ++i) {

        dp[i] = 0;

        for (int j = 0; j < i; ++j) {

            if (seg[j].r <= seg[i].l) dp[i] = max(dp[i], dp[j]);

        }

        dp[i] += seg[i].w;

        ans = max(ans, dp[i]);

    }

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

    return 0;

}

巴特西

Codevs 1643 & 3027 线段覆盖

1643

题意

思路

Code

3027

题意

思路

Code

最新文章

热门文章