2014-10-27

TIOJ::1811 . 書架

http://tioj.ck.tp.edu.tw/problems/1811
http://hoj.twbbs.org/judge/problem/view/203

這題是DP，聽了周強的說明後，又去翻了網路上的Code才終於大概了解了一點點，先寫下來，有錯再說XDD。

這題題目是，你有一堆書，然後你必須把他們收到一些書架上，書架有寬度限制，所以太多本書之後就必須要換書架，可是太多書架疊起來太高會很醜，所以你希望書架們疊起來越矮越好~~。每本書都有自己的高度和寬度，而一個書架的高度就是裡面最高的那本書。因為你有按照集數排好，所以你必須照著順序把書放到書架上。

看起來就一臉很DP的樣子。可是就是很難想到她長怎樣。

後來有個作法。
首先狀態就是， DP[N] 代表從1～N本書都排到書架上，最矮的高度是多少。
再來，要放 N+1 本書時會有兩種狀態轉移，也就是：

直接擺到下一個書架，DP[N+1] = DP[N] + H[N+1] ，H是書的高度。
接續在現在最好的排法後面擺，也就是 min(DP[ j ] + max( j～N+1 )，簡單說就是找現在最小的排法然後全部塞後面啦，這有一個限制條件，就是書櫃要夠大！

然後，單調隊列就出場了。因為我們可以觀察到一些性質，就是：
1.假設，L是在N+1擺的下去的情況下，最左邊的書，那麼我們已經可以確定L之前的書擺法都已經確定了，不用在管他了。
2.直接換行的時候，在N+1 和 [N、N-1….L+1] 裡第一個比N+1高的書(如果都比較矮的話就是L，因為她是邊界，只能選他)中間的書，無論是放在上一排後面，或是這一排的N+1前面，都不影響高度而且一定放的進去。
3.由於上述性質，我們可以維護一個嚴格遞減的單調隊列(假設為 dq)，代表在L後面最高的書。再增加一本書時，轉移式就變成 DP[dq.back()]+H[N+1] ，中間的書不用考慮，因為他們不影響高度。

另外一種狀態-接在後面，也因為第3點的關係，變成 DP[L] +H[dq.front()] ，也就是，把邊界之前的狀況確定之後，直接把最下面的這整排書架塞滿(一定放的下，N+1本書如果是最高的就會更新 dq，只有 dq 最前面的書在影響高度)，其中如果上一層空間夠，在邊界和最高的書中間的書可以任意移動到前一個書架上(因為不影響高度)。
以上的狀態中最小的就是 DP[N+1]。
可是，有時狀態會變成不合理的狀態，比如最高的不是他了’、或是N+2前面第一個比她高的改變了( 更新 dq 時，會在PUSH前先把小的POP掉，就會讓之前的狀態改變 )，對於這些不合理的狀態(對於N+2不合理，但是對N+1可能合理)，我們直接刪掉就好了。

所以只要更新狀態，刪掉不合理的狀態，再取min就可以得到DP值了。答案就是 DP[最後一本書]。
實際的細節，就是維護一個 dq ，其中比較特別的是， dq.front() 就是L，初值是0 (書從 1 開始編號， DP[0] 也是 0)，所以在維護遞減時，不能把他給砍了，因為這樣妳就沒有邊界了XD。
之後拿到一本書，就把dq後面比這本小的都POP掉(就單調隊列啊)，同時把第 1 種轉移中有用到這本書的狀態砍掉。再來把寬度加入一個變數中，判斷寬度有沒有超過，如果有，就把對應的狀態砍掉，然後把 L邊界加一，注意這裡不是直接POP(除非他加一後跟dq裡的第二個一樣)，因為他是邊界，他的意義只是我把整個 dq 當成最後一排書架放上去時，前面的書架狀態。

其實我覺得最難發現的觀念就是，這些狀態不一定是對那本書最好的，也可能兩個轉移都是浪費書架，但是如果後面還有書，這就有可能是最好的狀態了。

對於狀態，可以用 STL::set存，要刪掉就把值刪掉就好。
可是其實有些值雖然不合理，但是因為很大(連續換三次行之類的)，所以其實你可以不管她。所以可以改成用heap，我們可以發現，第1種轉移只要 dq.back()被POP就會跟著被刪掉，第2種轉移則是L被修改就會被刪掉，所以，用一個陣列記錄書在不在 dq 裡，然後 heap裡記錄 DP[X]+H[Y] –> X跟Y ，這兩個如果有哪個不再 dq 裡代表他不合法，就刪掉她。
這樣可以快一點點，但是相對的垃圾會留在heap裡。

Set

#include <iostream>
#include <queue>
#include <set>
#define N 100001
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define LL long long
using namespace std;
set<LL>ss;
deque<int>dq;
int H[N],W[N];
LL DP[N],sum;
main(){
    ios_base::sync_with_stdio(false);
    int n,L,le=0;
    cin>>n>>L;
    dq.push_back(0);
    Fl(i,1,n+1){
        cin>>H[i]>>W[i];
        while(dq.size()>1&&H[dq.back()]<=H[i]){
            int tmp=dq.back();dq.pop_back();
            ss.erase(DP[dq.back()]+H[tmp]);
        }
        ss.insert(DP[dq.back()]+H[i]);
        dq.push_back(i);
        sum+=W[i];
        while(sum>L){
            ss.erase(DP[dq[0]]+H[dq[1]]);
            sum-=W[++dq.front()];
            if(dq[0]==dq[1])dq.pop_front();
            else if(sum<=L)ss.insert(DP[dq[0]]+H[dq[1]]);
        }
        // puts("----");
  //       for(int hhh=0;hhh<dq.size();hhh++){
  //           cout<<dq[hhh]<<' '<<DP[dq[hhh]]<<' '<<(*ss.begin())<<endl;
  //       }
  //       puts("----");
        DP[i]=*ss.begin();
    }
    cout<<DP[n]<<endl;
    cin>>n;
}

Priority Queue

#include <iostream>
#include <queue>
#include <set>
#define N 100001
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define LL long long
using namespace std;
struct MP{
    int x,y;
};
priority_queue<MP>qq;
deque<int>dq;
int H[N],W[N];
bool INQ[N];
LL DP[N],sum;
bool operator<(MP a,MP b){
    return DP[a.x]+H[a.y]>DP[b.x]+H[b.y];
}
main(){
    ios_base::sync_with_stdio(false);
    int n,L,le=0;
    cin>>n>>L;
    dq.push_back(0);
    INQ[0]=true;
    Fl(i,1,n+1){
        cin>>H[i]>>W[i];
        while(dq.size()>1&&H[dq.back()]<=H[i]){
            int tmp=dq.back();dq.pop_back();
            INQ[tmp]=false;
        }
        qq.push((MP){dq.back(),i});
        dq.push_back(i);
        INQ[i]=true;
        sum+=W[i];
        while(sum>L){
            INQ[dq.front()]=false;
            sum-=W[++dq.front()];
            INQ[dq.front()]=true;
            if(dq[0]==dq[1])dq.pop_front();
            else qq.push((MP){dq[0],dq[1]});
        }
        while(!INQ[qq.top().x]||!INQ[qq.top().y])qq.pop();
        DP[i]=DP[qq.top().x]+H[qq.top().y];
    }
    cout<<DP[n]<<endl;
    cin>>n;
}