快被搞死了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]); }
