2015年6月5日 星期五

[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]) ;
}
 

沒有留言:

張貼留言