[CF 480D] Parcels

作法：

首先把每個箱子的進入時間和出去時間畫在數線上，轉換成一條線段，那麼可以到如果有兩個箱子都有出現在台子上，那麼要嘛一個箱子的線段完全包含另一個的，要嘛兩個箱子的線段不相交（端點可以碰到），或是說他會形成一個類似樹形結構的東西，所以大概可以想的到是某種DP。以下我們稱滿足上述條件的線段們為「合法的」，還有如果把這些線段（箱子）拿去模擬放在平台上的話平台所需支撐的最大重量為這群線段的「最大重量」。

我們要處理的問題是「在這個耐重$S$的台子上，使用那$n$條線段所獲得的最大價值」，因此我們可以加上第$n+1$個箱子，他對應的線段是$[0,2n-1]$，耐重是$S$。因此就可以考慮以下的DP狀態：$dp[i][j]$代表現在只考慮所有第$i$條線段所包含的線段（包括$i$本身），那麼當在這之中選出一群合法的線段，並且這群線段的「最大重量」不超過$j$時，所能獲得的最大價值。在轉移的部份，如果$i$沒有自己以外包含在他內部的線段，那麼他的所有$dp$值都是顯然的。否則第一種轉移方法是：不取第$i$條線段，此時我們可以選好幾條包含在$i$內的線段$S_1....,S_r$，滿足任兩條線段不相交（可以端點重合），轉移到$dp[S_1][j]+...+dp[S_r][j]$。另一種轉移方法則是取$i$，那麼就會直接等價於$dp[i][min(str[i],j-wei[i])]$的情形了，其中$str$代表那個線段的強度，$wei$則是代表重量。顯然第一種轉移沒辦法直接轉，這裡我們可以再用一個DP，因為當$i,j$確定時，對於所有包含在$i$內的線段$k$（$k\neq i$），取他的話等於價值增加了$dp[k][j]$，也就是會是固定的，因此這裡就可以轉換成簡單的問題：數線上有$m$條線段，每條線段都有他的價值，求取好幾條線段使得他們兩兩不相交（可以端點重合）的話價值總和的最大值。這顯然可以先對每條線段的右端點排序、離散化，然後令$dp2[i]=$只考慮線段座標落於$[1,x]$之類的線段時所能獲得的最大價值，則轉移是顯然的。

總結來說，可以先把所有線段按照右端點由小到大排序，一樣時按左端點由大到小排序，那麼上面說的DP過程就可以按照$1,2,...$的順序來做了。並且在作一條線段的DP值時，找出有哪些線段被他包含在裡面，假設有$k$條好了，那麼就可以在$O(klogk+Sk)$的複雜度內求出這條線段的所有DP值了，其中$S$是箱子們的最大強度。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
 
struct P
{
    int l,r,w,s,val,id ;
    void scan(){scanf("%d%d%d%d%d",&l,&r,&w,&s,&val) ;}
    bool operator < (const P &rhs) const
    {
        return r==rhs.r ? l>rhs.l : r<rhs.r ;
    }
}a[maxn] ;
 
vector<P> v ;
vector<int> v2 ;
void get_seg()
{
    v2.clear() ;
    for(auto i : v)
        v2.push_back(i.l) , v2.push_back(i.r) ;
 
    sort(v2.begin(),v2.end()) ;
    v2.resize(unique(v2.begin(),v2.end())-v2.begin()) ;
    for(auto &i : v)
        i.l=lower_bound(v2.begin(),v2.end(),i.l)-v2.begin()+1 ,
        i.r=lower_bound(v2.begin(),v2.end(),i.r)-v2.begin()+1 ;
    sort(v.begin(),v.end()) ;
}
 
int n,dp[maxn][maxn] ;
int dp2[maxn] ;
void DP(int x)
{
    for(int i=0;i<maxn;i++)
    {
        int sz=v2.size() ;
        fill(dp2,dp2+sz+1,0) ;
        for(int j=1,k=0;j<=sz && k<v.size();k++)
        {
            for(;j<v[k].r;j++) dp2[j]=max(dp2[j],dp2[j-1]) ;
            dp2[j]=max(dp2[j],dp2[j-1]) ;
            dp2[j]=max(dp2[j],dp2[v[k].l]+dp[v[k].id][i]) ;
        }
        dp[x][i]=dp2[sz] ;
    }
    if(x==n+1) return ;
    for(int i=maxn-1;i>=a[x].w;i--)
        dp[x][i]=max(dp[x][i],
        dp[x][min(i-a[x].w,a[x].s)]+a[x].val) ;
}
 
main()
{
    int S ;
    scanf("%d%d",&n,&S) ;
    for(int i=1;i<=n;i++) a[i].scan() ;
    sort(a+1,a+n+1) ;
    for(int i=1;i<=n;i++) a[i].id=i ;
 
    a[n+1]=(P){0,2*n-1,0,S,0} ;
    for(int i=1;i<=n+1;i++)
    {
        v.clear() ;
        for(int j=1;j<i;j++) if(a[j].l>=a[i].l)
            v.push_back(a[j]) ;
        get_seg() ;
        DP(i) ;
    }
 
    printf("%d\n",dp[n+1][S]) ;
}