【Codeforces 559E】Gerald and Path

相关链接

题目传送门：http://codeforces.com/contest/559/problem/E
官方题解：http://codeforces.com/blog/entry/19237
中文题面：http://blog.csdn.net/mengzhengnan/article/details/47057557

解题报告

这题官方题解是$O(n^4)$的
然而评论区给出了$O(n^3)$甚至$O(n^2)$的算法
不过评论区并没有给题解，只是扔了两份非常不可读的代码
于是我一个都没有懂 QwQ
后来自己想了一个$O(n^3)$的DP，来说一说吧！

考虑最常规的$DP$式子$f[i][j]$表示用了前$i$个路灯，已被照亮的区间的最右端点为$j$
这样的话，只有一种情况会出现问题：

ps:红色的部分会被漏掉
于是我们就预处理出所有路灯向左照的时候覆盖情况
因为超过第i个路灯的位置并且对答案有贡献的路灯最多一个
所以我们就可以枚举是那个路灯超过了i
这样的话，新增转移多了$n^2$个
又因为每一个转移会被使用$O(n)$次，于是总的时间复杂度为：$O(n^3)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300+9;

int n,tot,Hash[N],f[N][N];
struct Mat{int p,l;}m[N];
struct Trans{int l,r,mx;};
vector<Trans> t[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Val(int p, int l, int r) {
	if (r <= p) return 0;
	if (l >= p) return Hash[r] - Hash[l];
	return Hash[r] - Hash[p];
}

int main() {
	n = read(); 
	for (int i=1,p,l;i<=n;i++) {
		p = read(); l = read();
		Hash[++tot] = p;
		Hash[++tot] = p + l;
		Hash[++tot] = p - l;
		m[i] = (Mat){p,l};
	}
	auto cmp = [](const Mat &A, const Mat &B) {return A.p < B.p;};
	sort(m+1, m+1+n, cmp);
	sort(Hash+1, Hash+1+tot);
	tot = unique(Hash+1, Hash+1+tot) - Hash - 1;
	for (int i=1,r,l;i<=n;i++) {
		r = m[i].p; l = m[i].p-m[i].l;
		for (int j=1,cr,cl;j<i;j++) {
			if (l > m[j].p) continue;
			cr = max(r, m[j].p+m[j].l); cl = l;
			for (int k=j+1;k<i;k++) 
				cl = min(cl, m[k].p-m[k].l);
			cl = lower_bound(Hash+1, Hash+1+tot, cl) - Hash;
			cr = lower_bound(Hash+1, Hash+1+tot, cr) - Hash;
			t[j].push_back((Trans){cl,cr,i});
		}
		l = lower_bound(Hash+1, Hash+1+tot, l) - Hash;
		r = lower_bound(Hash+1, Hash+1+tot, r) - Hash;
		t[i].push_back((Trans){l,r,i});
		l = m[i].p; r = m[i].p + m[i].l;
		l = lower_bound(Hash+1, Hash+1+tot, l) - Hash;
		r = lower_bound(Hash+1, Hash+1+tot, r) - Hash;
		t[i].push_back((Trans){l,r,i});
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=tot;j++) 
			f[i][j] = max(f[i][j], f[i-1][j]);
		for (int k=t[i].size()-1,l,r,mx;~k;k--) {
			l = t[i][k].l; r = t[i][k].r; mx = t[i][k].mx;
			for (int j=1;j<=tot;j++) {
				if (j >= r) break;
				f[mx+1][r] = max(f[mx+1][r], f[i][j] + Val(j, l, r));
			}
		}
	}
	int vout = 0;
	for (int i=1;i<=n+1;i++) {
		for (int j=1;j<=tot;j++) {
			vout = max(vout, f[i][j]);
		}
	}
	printf("%d\n",vout);
	return 0;
}