相关链接
题目传送门：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;
}
