Problem surface

\(n \le 100\).

Problem solution

First, sort in ascending order according to the position of the end points. It is not difficult to think of the state \ (f_{i,j,op} \) to indicate that considering the first \ (I \) points, the line segment of the point \ (j \) is closest to the right of the right end point after orientation, and the orientation direction is the maximum length of \ (OP \) (\ (0 \) to the left and \ (1 \) to the right)

Note \ (R(pos,op) \) indicates that the line segment of point \ (pos \) is oriented to the right endpoint of \ (op \)

To transfer from \ (f {I, J, Op} \) to \ (f {i+1, R, D} \), if \ (i+1 \) goes to the right, \ (f {i+1, R, D} = f {I, J, Op} + min (len {i+1}, R (i+1,1) - R (J, OP)) \)

However, if we want to go to the left, we will find it difficult to do, because it may cover the gap between the previous two line segments, and this is not easy to calculate. We can only design the interval on the left of the state \ (R(j,op) \) to no longer allow contribution. At this time, it is found that \ (i+1 \) contains the line segment on the right, which inspires us to analyze from the four relationships of the line segment. We can only analyze \ (j \) first, and then generalize the more general method.

1. If \ (R(j,op)\le R(i+1,op1) \) and \ (L(j,op)\le L(i+1,op1) \), it is the above transfer formula

2. If \ (R(j,op)\ge R(i+1,op1) \) and \ (L(j,op)\ge L(i+1,op1) \), then \ (min (len {i+1}, r (i+1,1) - r (J, OP) \) is negative, which is equivalent to moving the right endpoint to \ (R(i+1,op1) \), plus \ (R(r,d)-R(i+1,op1) \) (because \ (r \) is to the left of \ (i+1 \), the following section must be continuous).

3. If \ ((j,op) \) contains \ ((i+1,op1) \), it is also the transfer form of the second type of case

We found that the above two transfer forms can actually be merged, that is

\(f_{i+1,r,d} = f_{i,j,op} + min(len_{i+1},R(i+1,1)-R(j,op)) + R(r,d)-R(i+1,op1)\)

1. If \ ((i+1,op1) \) contains \ ((j,op) \), then \ ((j,op) \) has no contribution. You can directly ignore it and transfer from the previous state. The transfer formula is also the one above. This neglect can obviously be pushed forward, that is, the new \ ((j,op) \) can be ignored after the state is pushed forward, so every time it is a state that has existed before. If you ignore too many, the answer will become smaller, so just count the status of all \ (R(j,op)\le R(i+1,op1) \).

So the transfer formulas of \ (R(j,op)\le R(i+1,op1) \) and \ (R(j,op)\ge R(i+1,op1) \) are the same!

Because we must ensure that \ ((j,op) \) is indeed the rightmost line segment, we adopt the contribution formula, \ (k \) constantly moves to the right, and greedily orient the ignored line segment to the right, and maintain \ (r,d \).

\(O(N^3)\)

Code

#include<bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
const int maxn = 110;
ll f[maxn][maxn][2];
int n;
struct range{
	int a,len; friend bool operator < (range x,range y){return x.a < y.a;}
}ran[maxn];
inline int rd(){
    int res=0,f=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
    for(;isdigit(ch);ch=getchar()) res=(res<<3)+(res<<1)+ch-48;
    return f?-res:res;
}
inline int R(int pos,int op){
	if(!pos) return -0x3f3f3f3f;
	return op ? ran[pos].a + ran[pos].len : ran[pos].a;
}
int main(){
	n = rd(); for(ri i = 1;i <= n;++i) ran[i].a = rd(),ran[i].len = rd();
	sort(ran + 1,ran + n + 1);
	memset(f,-1,sizeof(f));
	f[0][0][0] = f[0][0][1] = 0;
	for(ri i = 0;i < n;++i)
	    for(ri j = 0;j <= i;++j)
		for(ri op = 0;op <= 1;++op)
	 	    if(f[i][j][op] != -1){
			int r = j,d = op;

			for(ri k = i + 1;k <= n;++k){
   			    if(R(k,0) >= R(r,d)) r = k,d = 0;
				f[k][r][d] = max(f[k][r][d],f[i][j][op] + min(ran[k].len,R(k,0) - R(j,op)) + R(r,d) - R(k,0));
				if(R(k,1) >= R(r,d)) r = k,d = 1;
				f[k][r][d] = max(f[k][r][d],f[i][j][op] + min(ran[k].len,R(k,1) - R(j,op)) + R(r,d) - R(k,1));
			}
 		    }
	ll ans = f[n][n][1];
	for(ri i = 1;i <= n;++i) for(ri j = 0;j <= 1;++j) ans = max(ans,f[n][i][j]);
	printf("%lld\n",ans);
    return 0;
}