题解 CF559E 【Gerald and Path】
xht
2019-12-07 15:54:02
> [CF559E Gerald and Path](https://codeforc.es/contest/559/problem/E)
## 题意
- 有 $n$ 条线段。
- 每条线段给定其中一端的位置及长度。
- 求所有线段覆盖的最大长度。
- $n \le 100$。
## 题解
首先对一端位置排序。
考虑 dp，设 $f_{i,j,p}$ 表示考虑前 $i$ 条线段，最靠右的线段是第 $j$ 条，其方向为 $p$（$0$ 左 $1$ 右）。
考虑如何转移，从小到大枚举 $i$ 后面的线段以及它的方向，同时维护枚举过的线段中最靠右的线段以及它的方向。
设线段 $j$ 在 $p$ 方向的右端点是 $o$；此时枚举到线段 $k$，它的方向为 $q$，长度为 $l$，右端点是 $t$；枚举过的线段中最靠右的线段是 $x$，它的方向为 $y$，右端点是 $z$。
那么有转移 $f_{k,x,y} \leftarrow f_{i,j,p} + \min(l, t - o) + z - t$。
时间复杂度 $\mathcal O(n^3)$。
## 代码
```cpp
const int N = 107;
int n, ans, f[N][N][2];
pi a[N];
int main() {
rd(n);
for (int i = 1; i <= n; i++) rd(a[i].fi), rd(a[i].se);
sort(a + 1, a + n + 1);
a[0].fi = -1e9;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
for (int p = 0; p < 2; p++) {
ans = max(ans, f[i][j][p]);
int o = a[j].fi + p * a[j].se, mx = -1e9, x, y;
for (int k = i + 1; k <= n; k++)
for (int q = 0; q < 2; q++) {
int t = a[k].fi + q * a[k].se;
if (t > mx) mx = t, x = k, y = q;
f[k][x][y] = max(f[k][x][y], f[i][j][p] + min(a[k].se, t - o) + mx - t);
}
}
print(ans);
return 0;
}
```