[HOJ 203][USACO 2012 Gold] 書架

還蠻難想的題目@@

作法：

一開始可以想到O(n^2)的DP解，可以得到
dp[ i ] = min { dp[ j ] + max( h[ j+1],h[ j+2],...,h[ i ] ) } ，其中 j 滿足
w[ j+1]+...+w[ i ] <= L 。

這時再注意到，如果叫上式中的後面那一坨 H( j ) 好了，那麼會有很多 j 他們的 H( j ) 會一樣，而當兩個 H( j ) 一樣時，要取的就是 dp 值比較小的那個，而又可以證明 dp 值一定是遞增的 ( 1 ~ i 的情況一定會比 1 ~ i+1 的情況好 ) ， 所以對相同的 H( j ) 一定是取越左邊的 dp 值越好，所以可以用一個 stack 來維護這些東西，但我們還需要砍掉一些不符合的 j (就是會讓厚度超過 L 的 j )，所以會變成一個 deque 。實作上是用一個 multiset 裡面裝現在可能的候選值，這樣就可以再作完一些插入和刪除的操作之後直接得到候選值的最小值 ( 也就是 dp[ i ] ) 。阿在砍掉會讓厚度 > L 的 j 的時候用的方法也蠻神奇的，一直把左邊界往右推的感覺......總之這題 code 不長，但很需要想。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
int h[maxn],w[maxn] ;
LL sum[maxn],dp[maxn] ;
int deq[maxn];
multiset<LL> mst ;
 
main()
{
    int n,L ; scanf("%d%d",&n,&L) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&h[i],&w[i]) ;
    int l=0 , r=0 ;
    deq[r++]=0 ;
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+w[i] ;
        while(r>l+1 && h[deq[r-1]]<=h[i])
            mst.erase(mst.find(dp[deq[r-2]]+h[deq[r-1]])) , r-- ;
        mst.insert(dp[deq[r-1]]+h[i]) ;
        deq[r++]=i ;
 
        while(sum[i]-sum[deq[l]]>L)
        {
            mst.erase(mst.find(dp[deq[l]]+h[deq[l+1]])) ;
            if(++deq[l] == deq[l+1]) l++ ;
            else mst.insert(dp[deq[l]]+h[deq[l+1]]) ;
        }
        dp[i]=*mst.begin() ;
    }
    printf("%I64d\n",dp[n]) ;
}