bzoj1096: [ZJOI2007]仓库建设

《用单调性优化动态规划》

这个是分析，超详细

const int N = 1000010;
const DB Eps = 0.000001;
struct Node {
    int l, r, ch;
    Node() {}
    Node(int _l, int _r, int _ch) : l(_l), r(_r), ch(_ch) {}
};
int C[N], X[N], n;
LL S[N], Sum[N], Dp[N];

inline void Input() {
	int x, p;
    scanf("%d", &n);
    For(i, 1, n)
		scanf("%d%d%d", &x, &p, &C[i]), 
        S[i] = S[i - 1] + p, Sum[i] = Sum[i - 1] + (LL) x * p, X[i] = x;
}


inline LL Cost(int l, int r) {
    return (S[r] - S[l - 1]) * X[r] - (Sum[r] - Sum[l - 1]) + C[r];
}

inline LL Get(int i, int j) {
    return Dp[j] + Cost(j + 1, i);
}

inline int Find(Node &t, int i) {
    int l = t.l, r = t.r;
    #define check(m) (Get(m, t.ch) < Get(m, i))
    
    if(check(r)) return r;
    while(l + 1 < r) {
        int m = (l + r)/2;
        if(check(m)) l = m;
        else r = m;
    }
    
    #undef check
    return l;
}

inline void Solve() {
	deque<Node> Q;
    Dp[0] = 0, Q.pub(Node(1, n, 0));
    For(i, 1, n) {
		Node &x = Q.front(), t;
        Dp[i] = Get(i, x.ch);
        if(x.l < x.r) x.l++;
        else Q.pof();
        int T;
        while(sz(Q)) {
            t = Q.back();
            if(Get(t.l, i) <= Get(t.l, t.ch)) Q.pob();
            else {
                Q.back().r = T = Find(t, i);
                break;
            }
        }
        if(!sz(Q)) Q.pub(Node(i + 1, n, i));
        else if(T < n) Q.pub(Node(T + 1, n, i));
    }
    cout << Dp[n] << endl;
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1096");
	#endif
	Input();
	Solve();
	return 0;
}