CF559E Gerald and Path 题解
Visits: 297
题意
- 有 $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)$。
代码
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;
}