(SPOJ) SHELF - Book Shelves

http://www.spoj.com/problems/SHELF/en/

快被搞死了XDD

這裡先假設a_i = h_i

可以發現，列出後的DP式子長這個樣子：dp_i = min(dp_j + max(a_j, a_{j+1}, ...... , a_i))

再藉由一個很 greedy的性質：dp值是會遞增的，後面的max(a_j, a_{j+1}, ........, a_i) 隨著j的增加是遞減的！

那，我們就可以對於每個max_a，存下最左邊的DP值(最好的解)，並把這個東西丟進multiset裡面比較

有了一個新的a_i近來，我們就需要 "合併" 一些max_a！。

經由分析，可以發現：一個東西最多進去multiset兩次，理由是：被merge前一次，被merge後一次。

在想一想，就能寫出下面那噁心(?)的code了><

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <cassert>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
typedef pair<pii,LL> piii;

#define F first
#define S second
#define SZ(x) ((int)(x).size())

const int N = 1e5 + 6;

LL prew[N],preh[N];
LL dp[N];

int w[N],h[N];
LL a[N];

piii P(LL _a,LL _b,LL _c)
{
    return make_pair( make_pair(_a,_b),_c );
}

struct DisjointSet
{
    static const int N = 1e5 + 6;
    int p[N];
    int sz[N];
    int max_a[N];
    int left_most[N];
    void init(int n)
    {
        for (int i=0;n>=i;i++)
        {
            p[i] = i;
            sz[i] = 1;
        }
    }
    int Find(int x)
    {
        return p[x] == x?x:p[x] = Find(p[x]);
    }
    void set_a(int pos,int val)
    {
        pos = Find(pos);
        max_a[pos] = val;
    }
    void set_left_most(int pos,int val)
    {
        pos = Find(pos);
        left_most[pos] = val;
    }
    void Union(int x,int y)
    {
        x = Find(x);
        y = Find(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x,y);
        //x has smaller size
        max_a[y] = max(max_a[y],max_a[x]);
        left_most[y] = min(left_most[x],left_most[y]);
        sz[y] += sz[x];
        p[x] = y;
    }
    int query_max_a(int x)
    {
        x = Find(x);
        return max_a[x];
    }
    int query_left_most(int x)
    {
        x = Find(x);
        return left_most[x];
    }
} djs;

int main ()
{
    int n,l;
    scanf("%d %d",&n,&l);
    for (int i=1;n>=i;i++)
    {
        scanf("%d %d",&h[i],&w[i]);
        preh[i] = preh[i-1] + h[i];
        prew[i] = prew[i-1] + w[i];
        a[i] = h[i];
    }
    deque<int> dq;  // index
    multiset<LL> st;
    djs.init(n);
    int dead_end = 0;
    for (int i=1;n>=i;i++)
    {
        //popping XDD
        while (SZ(dq))
        {
            int t=dq.front();
            if (prew[i] - prew[t-1] <= l) break;
            dead_end = t;
            dq.pop_front();
            if (st.find(dp[t-1] + djs.query_max_a(t)) == st.end()) assert(0);
            st.erase(st.find(dp[t-1] + djs.query_max_a(t)));
            if (djs.Find(t+1) == djs.Find(t))
            {
                st.insert(dp[t+1-1] + djs.query_max_a(t+1));
                djs.set_left_most(t+1,t+1);
            }
        }
        //inserting
        djs.set_a(i,a[i]);
        djs.set_left_most(i,i);
        for (int t=i-1;t != dead_end;)
        {
            if (djs.query_max_a(t) > djs.query_max_a(i)) break;
            int left = djs.query_left_most(t);
            if (st.find(dp[left-1] + djs.query_max_a(left)) == st.end()) assert(0);
            st.erase(st.find(dp[left-1] + djs.query_max_a(left)));
            djs.Union(i,left);
            t = left-1;
        }
        dq.push_back(i);
        int ll=djs.query_left_most(i);
        st.insert(dp[ll-1] + djs.query_max_a(ll));
        dp[i] = (*st.begin());
    }
    printf("%lld\n",dp[n]);
}