描述

數(shù)軸上有n條線段，線段的兩端都是整數(shù)坐標(biāo)，坐標(biāo)范圍在0~10^18，每條線段有一個價值，請從n條線段中挑出若干條線段，使得這些線段兩兩不覆蓋（端點(diǎn)可以重合）且線段價值之和最大。

---

分析

提供兩種思路:

利用離散化. 因?yàn)檫@道題本來就是離散化的例題. 將點(diǎn)排序后依次賦值(1~2n, n為線段的條數(shù)), 再通過結(jié)構(gòu)體里的信息將離散化后的點(diǎn)的坐標(biāo)映射到線段上.

利用二分法直接DP. 看到題解里有二分兩個字, 自己YY出一套二分的做法不過好像和題解里的不一樣: 將線段按終點(diǎn)從小到大排序, 考慮線段i, 用 f[i][0] 記錄不選 i 的最大權(quán)值和, f[i][1] 記錄選擇 i 的最大權(quán)值和. 那么顯然有 f[i][0] = max{f[i-1][0], f[i-1][1]}. 然后二分 (upper_bound()) 查找最后一個可以接在 i 前的線段 j, 那么 f[i][1] = max{f[j][0], f[j][1]} + v[i].

不過尷尬的是第二種方法WA了四個點(diǎn)…而且差了不是一個數(shù)量級…

---

代碼

3791ms, 65MB

// 1. 離散化 #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 1000000 + 10;LL f[maxn<<1];struct Line { int s, t, v;bool operator < (const Line& rhs) const {if(t != rhs.t) return t < rhs.t;if(s != rhs.s) return s < rhs.s;return v < rhs.v;} }lines[maxn];struct Point {bool d; // d=0 -> on left; d=1 -> on rightLL pos; // previous positionint id, x; // id of the line, current positionbool operator < (const Point& rhs) const {return pos < rhs.pos;} }points[maxn<<1];int main() {int n;scanf("%d", &n);for(int i = 0; i < n; i++) {LL s, t;scanf("%lld%lld%d", &s, &t, &lines[i].v);points[i<<1] = (Point) {0, s, i};points[(i<<1)^1] = (Point) {1, t, i};}sort(points, points + 2*n);// discretizationint base = 0, cnt = 0;while(base < 2*n) {int cur = base;points[cur++].x = ++cnt;while(points[cur].pos == points[base].pos && cur < 2*n) points[cur++].x = cnt;base = cur;}for(int i = 0; i < 2*n; i++) {Point& P = points[i];if(P.d == 0) lines[P.id].s = P.x;else lines[P.id].t = P.x;}sort(lines, lines + n);LL ans = 0LL;for(int cur = 0, pre = 0; cur < n; cur++) {Line& L = lines[cur];if(L.t != pre) {for(int i = pre + 1; i <= L.t; i++) f[i] = f[pre];pre = L.t;}ans = max(ans, (f[L.t] = max(f[L.t], f[L.s] + L.v)));}printf("%lld\n", ans);return 0; }

---

// 二分 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 1000000 + 10;ll f[maxn][2], t[maxn];struct Line { ll s, t, v;bool operator < (const Line& rhs) const {if(t != rhs.t) return t < rhs.t;if(v != rhs.v) return v > rhs.v;return s > rhs.s;} }lines[maxn];int main() {int n;scanf("%d", &n);for(int i = 0; i < n; i++) {ll s, t, v;scanf("%lld%lld%lld", &s, &t, &v);lines[i] = (Line) {s, t, v};}sort(lines, lines + n);for(int i = 0; i < n; i++) t[i] = lines[i].t; // 用于二分查找 f[0][0] = 0; f[0][1] = lines[0].v;for(int i = 1; i < n; i++) {Line L = lines[i];f[i][0] = max(f[i-1][0], f[i-1][1]);int j = upper_bound(t, t + n, L.s) - t - 1;if(j >= 0) f[i][1] = max(f[j][0], f[j][1]) + L.v;else f[i][1] = L.v; // 前面沒有可以和它拼接的線段 }printf("%d\n", max(f[n-1][0], f[n-1][1]));return 0; } 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的[CODEVS 3037] 线段覆盖 5的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。