[CF559E]Gerald and Path

subject

Portal to CF

Ideas

generally speaking , We will sort the intervals . Because the interval is essentially Two dimensional partial order Relationship , Sort by endpoint It can make a certain dimension orderly , amount to Dimension reduction .

In this question , The interval is not very fixed . But there are two possible ranges ,$a_i$ Is a common endpoint ; So, in accordance with the $a_i$ Sorting is natural .

Next, consider $\mathtt{d}\mathtt{p}$ Transfer . For example, the current choice $[a_i-l_i,a_i]$, We need to find out its new coverage . however , In this large section , You may have chosen several short paragraphs , It is impossible to record all . What do I do ？

One idea is , Ignore the details . Don't use useless information $\mathtt{d}\mathtt{p}$ Status plug . The useful interval may be $[s_i,t_i](s_i<a_i-l_i<t_i)$ and $[s_i,t_i](s_i<a_i<t_i)$, That is, override prefix or suffix .

So let's enumerate an interval $p$, It covers a prefix , The rest of the interval cannot cover its right .$p$ It may be left , At this time, the only interval not to be ignored is $p$ The previous interval ;$p$ Maybe right , The interval that is not ignored is $[1,i)$ The range of , This $i$ And $p$ It doesn't matter. .

So let's not stick to one dimension $\mathtt{d}\mathtt{p}$, remember $f(p,i)$ To consider only $[1,i]$ Section 、$p$ Select the right section 、 Other sections do not cover $p$ To the right , Maximum coverage distance and . Transfer or use the same method , Enumerate the intervals that cover prefixes $j$, from $f(j,p-1)$ Turn around .

$g(p)$ To consider only $[1,p]$ Section 、$p$ Choose left in the interval 、 Other sections do not cover $p$ To the right , Maximum coverage distance and . By contrast , Its transfer is easier , Therefore, it is omitted here .

Time complexity $\mathcal{O}(n^3)$ . The code implementation is relatively smooth . You can't pass it if you hand it in , It has been debugged for a long time .

Code

There may be no interval covering the prefix , Therefore, it is best to let the initial value be the interval length （ It's equivalent to choosing only yourself ）.

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG long for LONELINESS)
#include <cctype> // ZXY yydSISTER!!!
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void getMax(int &x, const int &y){
    
	if(x < y) x = y;
}

const int MAXN = 105;
std::pair<int,int> a[MAXN];
int lef[MAXN], rig[MAXN][MAXN];

const int INF = 200000000;
int main(){
    
	int n = readint();
	rep(i,1,n) a[i].first = readint(), a[i].second = readint();
	std::sort(a+1,a+n+1); // sort by COORD
	for(int i=1; i<=n; ++i){
    
		lef[i] = a[i].second; // only itself
		for(int j=1; j!=i; ++j){
     // last longest
			if(a[j].first+a[j].second <= a[i].first)
				getMax(lef[i],rig[i-1][j]+min(a[i].first
					-a[j].first-a[j].second,a[i].second));
			getMax(lef[i],lef[j]+min(a[i].first-a[j].first,a[i].second));
		}
		int l = a[i].first; // whatever
		for(int j=i; j; --j){
     // my longest
			const int w = a[j].first+a[j].second;
			l = std::min(l,a[j].first); // itself's left point
			if(w >= a[i].first){
     // really longer
				rig[i][j] = w-l; // only itself
				for(int k=1; k!=j; ++k){
     // previous longest
					getMax(rig[i][j],rig[j-1][k]+w
						-max(a[k].first+a[k].second,l));
					getMax(rig[i][j],lef[k]+w-max(l,a[k].first));
				}
			}
			else rig[i][j] = rig[i-1][j]; // not to choose it
			l = min(l,a[j].first-a[j].second); // be toL
		}
	}
	int ans = lef[n]; // @a lef is non-decreasing
	rep(i,1,n) getMax(ans,rig[n][i]);
	printf("%d\n",ans);
	return 0;
}

Postscript

Modelled on the $\text{Lanterns}$ How to do it , Don't make decisions based on intervals , Make decisions based on coverage , At least it should be able to $\mathcal{O}(n^2\log n)$ . take $a_i-l_i,a_i,a_i+l_i$ Discretize together , Preprocessing $g(i,j)$ For whether the inner interval can be used to cover the $i$ Paragraphs to $j$ paragraph . For a $i$, use $\text{Lanterns}$ Approach is to $\mathcal{O}(n\log n)$ Of .

Pure mustard , It seems to be possible to do $\mathcal{O}(n^2)$ . because $\mathtt{S}\mathtt{T}$ Table is $\mathcal{O}(n\log n)$ Of , The bottleneck is , Find the shape as $h(i)⩾w_j$ Minimum $i$ . If you put $w_j$ Discrete out , For each $f(i)$ Immediately update what it can be transferred to $j$, There is no dichotomy process . Be careful $h(i)$ yes “ paragraph ” The number of , So it should be possible to pretreat $\mathcal{O}(1)$ Find out the updatable interval .

Last , In fact, there are $\mathcal{O}(n^2)$ Pure $\mathtt{d}\mathtt{p}$ practice , Has been $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ After seeing the question $10\mathrm{m}\mathrm{i}\mathrm{n}$ Internal thinking . I spent it. $2\mathrm{h}30\mathrm{m}\mathrm{i}\mathrm{n}$ Just think of $\mathcal{O}(n^3)$ .