[CF 559E] Gerald and Path

作法：

我們把一個路燈想像成一根直立的棍子，長度為他可以照到的範圍，那麼現在就變成我們要決定他們要往左倒還是往右倒，使得總覆蓋區間最大。假設現在我們已經全部決定好了，那麼倒下的棍子們會形成好幾陀連通塊（若兩根棍子有交集則在他們之間連邊，考慮這張圖可以獲得一些連通塊），首先不難發現每個連通塊一定都是由連續的棍子所組成的，因此我們可以考慮先求出$dp[i][j]$，代表「從第$i$根到第$j$根棍子倒下後若形成一個連通塊，那麼這個連通塊有哪些可能的左右端點」，也就是一個$dp[i][j]$其實一個 vector<pair<int,int>>，裡面存了很多條線段。這邊可以再發現，如果有兩條線段是互相包含的關係，那麼顯然外面的一定比裡面的還好，因此我們可以只留下必要的線段就可以了，也就是當左端點遞增時右端點也遞增的線段們。不難得知如果我們已經有了所有的$dp[i][j]$的線段，那麼最後就可以再用個DP求出答案了，因此接下來只要關注如何轉移就可以了。

首先當$i=j$的時候顯然有兩個線段，丟進去即可。假設現在我們要算$dp[i][j]$有哪些線段，我們可以先把一些候選的線段丟進$dp[i][j]$中，最後再一次處理掉剛才所說的「被別人包含的線段」。考慮枚舉斷點$k$，那麼我們現在有$dp[i][k]$的一堆線段，還有$dp[k+1][j]$的一堆線段，我們想要用他們合成出新的線段。我們可以先假設$dp[i][k]$裡的線段是被放在左邊的線段，因為可以等一下把$dp[i][k]$和$dp[k+1][j]$交換再作一次即可。考慮枚舉$dp[i][k]$中的線段，當左邊的線段確定後，因為$dp[k+1][j]$中的線段都是當左端點遞增時右端點也遞增的，因此我們只要想辦法找到$dp[k+1][j]$中「和此左線段有交集的右端點最大的線段」就可以了，這可以用一個 lower_bound 達成。這樣轉移複雜度為$O(n^2logn)$，總複雜度為$O(n^4logn)$，不過在 codeforces 上跑得很快，可能是因為線段數量沒有到每個 dp 陣列都$O(n)$那麼多。


code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100+10 ;
 
struct P
{
    int x,y ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ? y>rhs.y : x<rhs.x ;
    }
};
 
void normalize(vector<P> &vp)
{
    sort(vp.begin(),vp.end()) ;
    int sz=0 ;
    for(int i=0;i<vp.size();i++)
        if(!sz || vp[sz-1].y<vp[i].y)
        vp[sz++]=vp[i] ;
    vp.resize(sz) ;
}
 
vector<int> v ;
inline int ID(int x)
{
    return lower_bound(v.begin(),v.end(),x)-v.begin() ;
}
 
void trans(vector<P> &v1,vector<P> &v2,vector<P> &ret)
{
    for(auto it : v1)
    {
        int id=lower_bound(v2.begin(),v2.end(),(P){it.y,-1})-v2.begin() ;
        if(!id || v2[--id].y<it.x) continue ;
        ret.push_back((P){min(it.x,v2[id].x),max(it.y,v2[id].y)}) ;
    }
}
 
vector<P> dp[maxn][maxn] ;
P a[maxn] ;
int dp2[maxn][3*maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y) ;
        for(int j=-1;j<2;j++) v.push_back(a[i].x+j*a[i].y) ;
    }
    sort(a+1,a+n+1) ;
    sort(v.begin(),v.end()) ;
    v.resize(unique(v.begin(),v.end())-v.begin()) ;
    for(int i=n;i>=1;i--) for(int j=i;j<=n;j++)
    {
        if(i==j)
        {
            dp[i][j].push_back((P){ID(a[i].x-a[i].y),ID(a[i].x)}) ;
            dp[i][j].push_back((P){ID(a[i].x),ID(a[i].x+a[i].y)}) ;
            continue ;
        }
        for(int k=i;k<j;k++)
            trans(dp[i][k],dp[k+1][j],dp[i][j]) ,
            trans(dp[k+1][j],dp[i][k],dp[i][j]) ;
        normalize(dp[i][j]) ;
    }
    for(int i=1;i<=n;i++) for(int j=0;j<v.size();j++)
    {
        dp2[i][j]= j ? dp2[i][j-1] : -2e9 ;
        for(int i2=0;i2<i;i2++) for(auto it : dp[i2+1][i])
        {
            if(it.y>j) break ;
            dp2[i][j]=max(dp2[i][j],
                dp2[i2][it.x]+v[it.y]-v[it.x]) ;
        }
    }
    printf("%d\n",dp2[n][v.size()-1]) ;
}