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)

Posted by xiaodao
Category: 日常