某岛

… : "…アッカリ~ン . .. . " .. .
December 28, 2012

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)