CF559E Gerald and Path 题解

作者: xht37 分类: 题解 发布时间: 2019-12-06 17:10

Visits: 212

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注