CF559E Gerald and Path

IOI2020集训队作业

小清新?这还是在跳过那倒计算几何题前提下....不过也很容易第一眼就误解

有 $n$ 条线段。
每条线段给定其中一端的位置及长度。
求所有线段覆盖的最大长度。
$n \le 100$ 。

你直接离散化想统计答案是不行的,为什么不行?因为你没法决定每条线段是向左还是向右更优

所以要DP(

设f_{i,j}表示前i条线段,最右端覆盖到j的覆盖最长长度是什么,然后我们考虑i线段是向左延伸还是向右延伸...

case 1 向右延伸

这种情况不会和之前做的决策产生冲突,所以直接转移即可

$f_{i,j}=max{f_{i-1,p}+dist(p,j)},j \in [p,r]$

case 2 向左延伸

这种情况可能和之前决策产生重叠然后自闭掉....

所以因为可能这样存在一些线段使他们原本的右端点在更右边,因为我们第二维是只有考虑前i-1条线段的情况

我们直接枚举 $k$ 并令 $k\sim i-1$ 这些线段都向右放。令 $R$ 表示右端点最右的位置。则 $f_{i,j}=\max\{f_{k-1,l}+\mathrm{dist}(l,R)\}$

这样子转移就不会有冲突问题了,注意我们处理的前提是我们可以考虑一条线段的长度不固定,也就是说题目中给出的是最大长度,这样我们的状态才能够贴切实际情况

直接枚举的复杂度为 $O(n^3)$ 。考虑 $k$ 从大到小枚举，更新 $R$ 的值。令 $g[R]$ 表示右端点为 $R$ 时的最大答案。

我们直接算出 $g[R]$ 后，还要对其做一遍后缀的处理。就是相当于取前缀计算贡献。具体可以见代码里的处理。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
vector<int> vec;
const int MAXN = 215;
struct rec {
	int l, r, p;
	inline bool operator<(const rec &x) const {
		return p < x.p;
	}
} d[MAXN];//线段

int n, f[MAXN][MAXN * 3], g[MAXN * 3];

inline int find(int &x) {
	x = lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

int main() {
	scanf("%d", &n);
	vec.push_back(-1e9);
	for(int i = 1; i <= n; ++i) {
		int a, l;
		scanf("%d%d", &a, &l);
		d[i] = (rec) {
			a - l, a + l, a
		};
		vec.push_back(d[i].l);
		vec.push_back(d[i].r);
		vec.push_back(d[i].p);
	}
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for(int i = 1; i <= n; ++i)find(d[i].l), find(d[i].r), find(d[i].p);
    //以上部分我们离散化
	int m = vec.size() - 1;
	sort(d + 1, d + n + 1);
	for(int i = 1; i <= n; ++i) {
		memcpy(f[i], f[i - 1], sizeof * f);
        //这里要开始DP
		int L = d[i].l, R = d[i].r, p = d[i].p;
		memset(g, 0, sizeof(g));
		int nr = p;
		g[nr] = f[i - 1][L] + vec[nr] - vec[L];
        //这里先更新i向左覆盖的答案
		for(int j = i - 1; j; --j) {
            //把i-1到0所有线段考虑向右最多能覆盖到哪里
			nr = max(nr, d[j].r);
			g[nr] = max(g[nr], f[j - 1][L] + vec[nr] - vec[L]);
            //计算新的贡献,用上这条线段
		}
		for(int j = m; j >= L; --j) {
			f[i][j] = max(f[i][j], g[j]);
            //更新新的答案,这条线段加进去可能会有所不同
			g[j - 1] = max(g[j - 1], g[j] - vec[j] + vec[j - 1]);
            //更新这个g数组,表示我们可以考虑把j点的答案去掉
		}
		for(int j = p; j <= R; ++j)f[i][j] = max(f[i][j], f[i - 1][p] + vec[j] - vec[p]);
        //在考虑有多点就好
		for(int j = 1; j <= m; ++j)f[i][j] = max(f[i][j], f[i][j - 1]);
	}
	printf("%d\n", f[n][m]);
	return 0;
}

咕咕咕

夏晓光(loveJY)的博客

case 1 向右延伸

case 2 向左延伸

CF547E Mike and Friends