subject

Portal to CF

thinking

Generally speaking, we will sort intervals. Because the interval is essentially a two-dimensional partial order relationship, sorting according to the endpoint can make a dimension orderly, which is equivalent to dimension reduction.

In this question, the interval is not very fixed. But of the two possible ranges, a i a_i ai is the common endpoint; So according to a i a_i ai# sorting is natural.

Next consider d p \tt dp dp transfer. For example, the current selection [ a i − l i , a i ] [a_i-l_i,a_i] [ai − li, ai], we need to find its new coverage. However, in this large range, several small segments may be selected, and it is impossible to record them all. What should I do?

One idea is to ignore the details. Don't use useless information d p \tt dp Plug in dp state. The useful interval may be [ s i , t i ]    ( s i < a i − l i < t i ) [s_i,t_i]\;(s_i<a_i-l_i<t_i) [si, ti] (si < AI − li < ti) and [ s i , t i ]    ( s i < a i < t i ) [s_i,t_i]\;(s_i<a_i<t_i) [si, ti] (si < AI < ti), i.e. covering prefix or suffix.

So let's enumerate an interval p p p. It covers a prefix, and the rest of the interval cannot cover its right. p p p may be left. At this time, the only interval that will not be ignored is p p Interval before p; p p p may be right, and the interval that is not ignored is [ 1 , i ) [1,i) [1,i) interval, this i i i and p p p doesn't matter.

So let's not stick to one dimension d p \tt dp dp, remember f ( p , i ) f(p,i) f(p,i) is only considered [ 1 , i ] [1,i] [1,i] interval p p p select the right of the interval, and other intervals are not covered p p To the right of p, the sum of the longest coverage distance. The transfer still uses the same method to enumerate the intervals covering the prefix j j j. From f ( j , p − 1 ) f(j,p{\rm-}1) Transfer f(j,p − 1).

g ( p ) g(p) g(p) is only considered [ 1 , p ] [1,p] [1,p] interval p p p select left for the interval, and other intervals are not covered p p To the right of p, the sum of the longest coverage distance. In contrast, its transfer is easier, so it is omitted here.

Time complexity O ( n 3 ) \mathcal O(n^3) O(n3) . The code implementation is relatively smooth. It's too late to hand it in. It's been debugged for a long time.

code

There may not be an interval covering the prefix, so it is best to make the initial value as the interval length (equivalent to selecting 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

Imitate Lanterns \text{Lanterns} Lanterns Instead of taking the interval as the decision-making, take the coverage as the decision-making, at least it should be able to do so O ( n 2 log ⁡ n ) \mathcal O(n^2\log n) O(n2logn) . take a i − l i ,    a i ,    a i + l i a_i-l_i,\;a_i,\;a_i+l_i ai − li, ai, ai + li − discretization together, preprocessing g ( i , j ) g(i,j) g(i,j) is whether the internal interval can cover the second section i i Paragraphs i to j j Paragraph j. For a i i i. Use Lanterns \text{Lanterns} Lantens's approach is O ( n log ⁡ n ) \mathcal O(n\log n) O(nlogn).

Pure mustache, it seems that you can do it O ( n 2 ) \mathcal O(n^2) O(n2) . because S T \tt ST ST table is O ( n log ⁡ n ) \mathcal O(n\log n) The bottleneck of O(nlogn) is to find the shape such as h ( i ) ⩾ w j h(i)\geqslant w_j Minimum of h(i) ⩾ wj ⩾ i i i . If you put it first w j w_j For each wj, discretization f ( i ) f(i) f(i) immediately update what it can transfer to j j j. There is no dichotomy. be careful h ( i ) h(i) h(i) is the number of "segment", so it should be available after preprocessing O ( 1 ) \mathcal O(1) O(1) find out the updatable interval.

Finally, there is O ( n 2 ) \mathcal O(n^2) Pure of O(n2) d p \tt dp dp practice has been O U Y E \sf OUYE OUYE after seeing the question 10 m i n 10\rm min Within 10min. I spent 2 h 30 m i n \rm 2h30min 2h30min only O ( n 3 ) \mathcal O(n^3) O(n3) .