[UVa 1106][ACM-ICPC World Finals 2011]Machine Works

這裡提供另外一種作法，選個你喜歡的去實現吧～

首先，先把機器依照購買時間排序，那麼就可以設計一個$DP$，$DP[i]$代表到達第i台機器的購買時間之前，賣掉所有機器可獲得的最大收入

為了方便說明，定義$M_{i}$為排序後的第i台機器
$M_{i}.day$代表這台機器的購買時間
$M_{i}.price$代表這台機器購入的價格
$M_{i}.resell$代表這台機器賣出的價格
$M_{i}.profit$代表這台機器每天能產生的利潤

可以發現，當購入第$i$台機器並開始無止盡的運作，你的錢隨著時間變化會是一條斜率$>0$的斜直線，而這條斜直線會和$x=Mi.day$交叉於$y=DP[i]+(Mi.resell−Mi.price)$，因此截距是$DP[i]+(Mi.resell−Mi.price)−Mi.profit∗Mi.day$ (看看DP的定義，想一想，為甚麼XD)

首先，如果我們知道$DP[a]、DP[a+1]、...、DP[b]$，我們就可以拿第$a\sim b$台機器賺最多的錢去分別更新第$b+1\sim N$台機器的最大值了
$_{註1}$考慮使用單調凸包優化$DP$，把第$a\sim b$台機器依照賺錢速度 (斜率) 排序，這樣一來，和這個做法不一樣的是，我們多了斜率的單調性，不用再做麻煩的二分搜和平衡樹動態增刪值了！

透過$deque$ (之後會發現只用到$stack$的功能，因為可以先做好凸包，才開始更新) 實作凸包優化$DP$，我們可以實現複雜度$O(n+m)$(假設拿$n$台機器去更新之後的其中$m$台機器)的更新

問題是，要用哪些機器來更新哪些機器呢(才不會讓複雜度退化)？

我們使用操作分治的思想
首先，如果我們知道了$DP[1]$，就可以拿去更新$DP[2]$ ($DP[2]$確定了)
我們知道了$DP[1]$和$DP[2]$，就去更新$DP[3]$和$DP[4]$ ($DP[3]$確定了)
這下$DP[3]$也確定了，因此拿去更新$DP[4]$ ($DP[4]$確定了)
這下我們知道了$DP[1]$、$DP[2]$、$DP[3]$和$DP[4]$，就去更新$DP[5]$、$DP[6]$、$DP[7]$和$DP[8]$ ($DP[5]$確定了)
......

有點倍增的感覺對不對？
可以發現，以上的做法可以看做是在一棵線段樹上依照遍歷順序，拿左子樹包含的區間 (可以保證這時左子樹的所有$DP$都已經確定了，想一想，為甚麼XD) 去一口氣更新右子樹包含的區間

知道了用甚麼順序更新，使用$_{註1}$講的方法，處理線段樹 (我覺得這裡還是要強調一下，這棵「線段樹」只是提供想像上的框架，不用真的建出來) 的每一層的時間複雜度是$O(N)$ (想一想，為甚麼XD)

總時間複雜度：$O(N\log N)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
void getmax(LL &a,const LL &b){if(b>a)a=b;}
struct Machine
{
    LL day,price,resell,profit;
    Machine(){}
    Machine(const LL &_day,const LL &_price,const LL &_resell,const LL &_profit):day(_day),price(_price),resell(_resell),profit(_profit){}
};
struct Deq
{
    int s[100002],l,r;
    void clear(){l=0,r=-1;}
    void push_back(const int v){s[++r]=v;}
    void pop_back(){r--;}
//    void pop_front(){l++;}//這個不會用到 
    int size(){return r-l+1;}
    int operator[](const int i)const{return s[l+i];}
    int back(const int i){return s[r-i];}
}DEQ;
vector<Machine>MACHINE;
LL DP[100002];
LL GetA(const int i){return MACHINE[i].profit;}
LL GetB(const int i)
{
    const Machine &m=MACHINE[i];
    return DP[i]+(m.resell-m.price)-m.profit*m.day;
}
double GetX(const int i1,const int i2){assert(GetA(i1)!=GetA(i2));return (double)(GetB(i1)-GetB(i2))/(GetA(i2)-GetA(i1));}
int N,D;
void Query(const vector<int>&machines)
{
    if((int)machines.size()==1)return;
    assert(!machines.empty());
    const int half=(int)machines.size()/2;
    vector<int>left_machines,right_machines;
    for(int i=0;i<(int)machines.size();i++)(i<half?left_machines:right_machines).push_back(machines[i]);
    Query(left_machines);
    sort(left_machines.begin(),left_machines.end(),[](const int a,const int b)->bool{return GetA(a)<GetA(b);});
    DEQ.clear();
    const auto &lm=left_machines;
    for(int i=0;i<(int)lm.size();i++)
    {
        if(DP[lm[i]]<MACHINE[lm[i]].price)continue;//買不起這台機器 
        if(DEQ.size()&&GetA(DEQ.back(0))==GetA(lm[i]))//注意斜率相同的情況 
        {
            if(GetB(DEQ.back(0))<=GetB(lm[i]))DEQ.pop_back();
            else continue;
        }
        while(DEQ.size()>=2&&GetX(DEQ.back(0),lm[i])<=GetX(DEQ.back(1),DEQ.back(0)))DEQ.pop_back();
        DEQ.push_back(lm[i]);
    }
    if(DEQ.size())
    {
        for(int i=2;i<DEQ.size();i++)assert(GetX(DEQ[i-2],DEQ[i-1])<=GetX(DEQ[i-1],DEQ[i]));
        const auto &rm=right_machines;
        for(int i=0,j=0;j<(int)rm.size();i++)
        {
            for(;j<(int)rm.size()&&(i+1==DEQ.size()||GetX(DEQ[i],DEQ[i+1])>=MACHINE[rm[j]].day-1LL);j++)
                getmax(DP[rm[j]],GetA(DEQ[i])*(MACHINE[rm[j]].day-1LL)+GetB(DEQ[i]));
        }
    }
    Query(right_machines);
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    while(scanf("%d%lld%d",&N,&DP[0],&D)==3)
    {
        if(N==0&&DP[0]==0LL&&D==0)break;
        MACHINE.clear(),MACHINE.push_back(Machine(0LL,0LL,0LL,0LL));
        for(int i=1,d,p,r,g;i<=N;i++)assert(scanf("%d%d%d%d",&d,&p,&r,&g)==4),MACHINE.push_back(Machine(d,p,r,g));
        for(int i=1;i<=N+1;i++)DP[i]=DP[0];
        MACHINE.push_back(Machine(D+1LL,0LL,0LL,0LL));
        sort(MACHINE.begin(),MACHINE.end(),[](const Machine &a,const Machine &b)->bool{return a.day<b.day;});
        assert(MACHINE[0].day==0LL);assert(MACHINE[N+1].day==D+1LL);
        assert((int)MACHINE.size()==N+2);
        vector<int>machines;
        for(int i=0;i<=N+1;i++)machines.push_back(i);
        Query(machines);
        static int kase=1;
        printf("Case %d: %lld\n",kase++,DP[N+1]);
    }
    return 0;
}