HDU 3842. Machine Works

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=23094

Brief description:

。。。某個工廠同一時刻最多只可以裝載一種機器,
。。。機器有買入價格,賣出價格,和每日利潤。
。。。有 n 個可以買入機器的時點。。每個時點形如,d, p, r, g 。。。
。。。分別表示時刻,買入價格,賣出價格和該機器的日利潤。

。買入只能在那個時刻進行,而賣出可以選擇買入後的任意時刻。
。給定初始時刻的金幣,問 d 天后所能獲得金幣的最大值。

Analysis:

原題中的兩個不太自然的條件。。
1. 任何時刻只能保留至多一台機器。
2. 機器賣出的收益是固定的,與日期無關。。

綜合上述兩個條件不難得到 O(n2) 的暴力 DP。。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2838582

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
LL f[N];

struct Event{
    int d,p,r,g; // 買入時間,買入價格,賣出價格,日利潤。
    bool operator <(const Event& rhs)const{
        return d < rhs.d;
    }
    void in(){
        RD(d,p,r,g);
    }
} E[N];

int n, d;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (RD(n, f[0], d)){
        REP_1(i, n) E[i].in(); sort(E+1, E+n+1); ++n; E[n].d = d+1; E[n].p = E[n].g = 0;

// b = kx + y

#define k (LL)E[i].d
#define x E[j].g
#define y (f[j]+E[j].r-E[j].p-(LL)x*(E[j].d+1))

        REP_1(i, n){
            f[i] = f[i-1]; REP(j, i) if (f[j] >= E[j].p){
                checkMax(f[i], k*x + y);
            }
        }
        OT(f[n]);
    }
}

寫成斜率 DP 的標準形式,注意到這裡 k, x 均不單調,無法使用單調隊列優化。。

方法一:
Splay 維護凸殼。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=880923 (注意用叉積。。。
500ms O(nlogn)

方法二:
cdq 分治

洲妹告訴我們。。這類問題都可以用 cdq 分治來解決。。。
。。。
通過 cdq 分治。。將原本需要強制在線的詢問。。可以離線處理。。。於是可以通過排序、重新讓詢問單調。。
。。重新讓棧隨便搞搞就能解決、、。。。。。。。。從而極大的降低了編程難度。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2795801
(1640ms。。。O(nlog2n)