CF559E Gerald and Path 题解

CF559E Gerald and Path

题意

• 有 $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;
}