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

不知道為甚麼這個人這麼坎坷，總之我寫完後debug了一下就AC了

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

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

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

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

因此，我們需要在一堆直線中，對於特定的$x$，找$y$的最大值
如果我們維護了一個下凸包，那$y$的最大值不就在這個凸包上嗎？

因此，我們需要維護哪些直線是在這個凸包上面
我們可以慢慢的把直線一條條加入，於是有了以下幾種情形：
1. 不影響凸包
2. 截掉凸包的一部分，有些線可能會被從凸包移除

加入線時，需要對斜率進行二分搜，因此開一個map維護斜率對應直線
詢問某個$x$的最大值時，需要對兩兩直線的交點的$x$座標進行二分搜，因此再開一個map維護交點對應直線

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

code:

#include<cstdio>
#include<cassert>
#include<set>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long LL;
//void assert(bool valid){if(valid)return;for(;;)putchar('E');}
struct Machine
{
    LL day,price,resell,profit;
    Machine():day(),price(),resell(),profit(){}
    Machine(const LL &_day,const LL &_price,const LL &_resell,const LL &_profit):day(_day),price(_price),resell(_resell),profit(_profit){}
    bool operator<(const Machine &m)const{return day<m.day;}
};
vector<Machine>MACHINE;
int N,D;
LL DP[100001];
LL GetA(const int i){return MACHINE[i].profit;}
LL GetB(const int i)
{
    const Machine &m=MACHINE[i];
    return DP[i]-m.profit*m.day+(m.resell-m.price);
}
double GetX(const int i1,const int i2){return (double)(GetB(i1)-GetB(i2))/(GetA(i2)-GetA(i1));}
struct LineComparer{bool operator()(const int i1,const int i2){return GetA(i1)!=GetA(i2)?GetA(i1)<GetA(i2):i1<i2;}};
set<int,LineComparer>DEQ;
map<double,set<int,LineComparer>::iterator>LOC,SLOPE;
void Erase(map<double,set<int,LineComparer>::iterator>&m,const double &v)
{
    auto it=m.find(v);
    assert(it!=m.end());
    m.erase(v);
}
void Erase(set<int,LineComparer>::iterator itd)
{
    if(true)
    {
        auto itdr=itd,itdl=itd;itdr++;
        if(itdl!=DEQ.begin()&&itdr!=DEQ.end())itdl--,LOC[GetX(*itdl,*itdr)]=itdl,itdl++;
        if(itdl!=DEQ.begin())itdl--,Erase(LOC,GetX(*itdl,*itd)),itdl++;
        if(itdr!=DEQ.end())Erase(LOC,GetX(*itd,*itdr));
    }
    Erase(SLOPE,GetA(*itd));
    DEQ.erase(itd);
}
void Insert(set<int,LineComparer>::iterator itd,const int i)
{
    if(true)
    {
        auto itdl=itd,itdm=itd;
        if(itdl!=DEQ.begin())
        {
            itdl--,itdm--;
            for(;;)
            {
                if(itdl==DEQ.begin())break;
                itdl--;
                if(GetX(*itdl,*itdm)<GetX(*itdm,i))break;
                auto tmp=itdm;itdm--;
                Erase(tmp);
            }
        }
    }
    if(true)
    {
        auto itdm=itd,itdr=itd;
        if(itdr!=DEQ.end())
        {
            itdr++;
            while(itdr!=DEQ.end()&&GetX(i,*itdm)>=GetX(*itdm,*itdr))
            {
                auto tmp=itdm;itdm++,itdr++;
                Erase(tmp);
            }
        }
    }
    DEQ.insert(i);
    itd=DEQ.find(i);
    assert(itd!=DEQ.end());
    SLOPE[GetA(i)]=itd;
    auto itdl=itd,itdr=itd;itdr++;
    if(itdl!=DEQ.begin()&&itdr!=DEQ.end())itdl--,Erase(LOC,GetX(*itdl,*itdr)),itdl++;
    if(itdl!=DEQ.begin())itdl--,LOC[GetX(*itdl,*itd)]=itdl,itdl++;
    if(itdr!=DEQ.end())LOC[GetX(*itd,*itdr)]=itd;
}
void Insert(const int i)
{
    auto its=SLOPE.lower_bound(GetA(i));
    if(its==SLOPE.end())
    {
        Insert(DEQ.lower_bound(i),i);
    }
    else if(GetA(*(its->second))==GetA(i))
    {
        if(GetB(i)>GetB(*(its->second)))
        {
            Erase(its->second);
            Insert(DEQ.lower_bound(i),i);
        }
    }
    else
    {
        auto itd=its->second;
        assert(itd!=DEQ.begin());
        auto itdl=itd;itdl--;
        if(GetA(i)*GetX(*itdl,*itd)+GetB(i)>GetA(*itdl)*GetX(*itdl,*itd)+GetB(*itdl))Insert(DEQ.lower_bound(i),i);
    }
//    printf("(%d,%d,%d)\n",(int)DEQ.size(),(int)LOC.size(),(int)SLOPE.size());
    assert(DEQ.size()==LOC.size()+1&&DEQ.size()==SLOPE.size());
}
LL QueryBase(const LL &x)
{
    auto itl=LOC.lower_bound(x);
    if(itl==LOC.end())
    {
        auto itd=DEQ.end();itd--;
        return GetA(*itd)*x+GetB(*itd);
    }
    auto itd=itl->second;
    return GetA(*itd)*x+GetB(*itd);
}
LL Query(const LL &x)
{
    const LL ans=QueryBase(x);
//    for(const auto it:DEQ)assert(GetA(it)*x+GetB(it)<=ans);
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    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++)scanf("%d%d%d%d",&d,&p,&r,&g),MACHINE.push_back(Machine(d,p,r,g));
        sort(MACHINE.begin(),MACHINE.end());
        DEQ.clear(),LOC.clear(),SLOPE.clear();
        Insert(0);
        for(int i=1;i<=N;i++)
        {
            const Machine &m=MACHINE[i];
            DP[i]=Query(m.day-1LL);
//            printf("DP[%d]=%lld\n",i,DP[i]);
            if(m.price>DP[i])continue;
            Insert(i);
//            for(const auto v:DEQ)printf("%d ",v);puts("");
        }
        static int kase=1;
        printf("Case %d: %lld\n",kase++,Query(D));
//        for(int i=MACHINE[N].day;i<=D;i++)printf("Query(%d)=%lld\n",i,Query(i));
    }
    return 0;
}