[Uva 1106][DP] Machine Works

原題連結
這道題目真是我見過最坑爹的一道題......

很容易想出狀態表示和轉移：
    dp[i]代表第i天時賣掉手上機器能獲得的最大金錢
    則dp[i]=max((t_i-t_j-1)*g_j+r_j-p_j+dp[j]),0<=j<i && dp[j]>=p_j (也有其他表示法，大同小異)
展開化簡有
dp[i]=max(g_j*t_i + (r_j-p_j+dp[j]-(t_j+1)*g_j)),0<=j<i && dp[j]>=p_j
有點經驗的人大概也看得出來是個1D/1D套凸包優化的節奏。

和 這篇 不一樣的地方只差在斜率沒有單調性罷了。

罷了？
罷了？
罷了？

因為沒有單調性所以只能用平衡樹來維護凸包線，並且手動實做查詢最大值，插入直線，刪除直線。
不過我們想要在插入直線的同時往左右檢查是否讓某些直線從凸包上消失，我們需要像STL的set::iterator一樣可以作到++,--之類對應到序列上的操作。
但是手刻Treap要想做到這種事情很難寫，別忘了還要思考在這棵Treap上怎麼二分搜最大值。
我寫到一半就非常睿智(?)的放棄手刻平衡樹了。

然後採用的是STL的set包Line，但是這樣要怎麼二分搜呢？只好再多存一個set<Point>了！用DB x,y把點表示出來，然後在維護直線的時候同時維護點。
寫完debug完之後過了範測和自產小測資，這樣就可以AC了！.....嗎？
因為原題的數值都可以到10^9，一個不小心浮點數誤差就會讓你刪錯點！
用eps輔助判斷呢？還是不會過！在二分搜最大值的時候很容易因為累積誤差使答案+,-1

那沒辦法了，只好用兩條直線表示一個點，然後手算出<的比較式子，這樣就可以完全避免浮點數。

然後就開心AC了嗎？太天真啦！
自產大型測資後會發現答案跟標程跑出來的答案怎麼比都怪怪的，於是在做的過程中把點和線的set列出來觀察一下。
怎麼看都沒有問題......
幾個小時候你發現直線的斜率雖然在10^9以內，截距卻有可能漲到10^11以上！

他會爆long long!!!!!!而點的<運算依賴斜率和截距相乘來比較大小，一旦比爛了set的lower_bound就跟廢物一樣了。

所以把LL改成__int128，調整一下輸入輸出，終於獲得了AC。
(以上過程約莫三天沒日沒夜的coding，請勿輕易嘗試)

#include<bits/stdc++.h>
#define LL __int128
using namespace std;
const LL maxn=100000+10;
struct Line
{
    LL slope,inter;
    Line(LL a,LL b):slope(a),inter(b) {}
    LL getVal(LL x) {return slope*x+inter;}
    bool operator < (const Line& rhs) const {return slope<rhs.slope || (slope==rhs.slope && inter<rhs.inter);}
};
struct Point
{
    Line L1,L2;
    Point(Line _L1,Line _L2):L1(_L1),L2(_L2) {}
    bool operator < (const Point& rhs) const
    {
        return (L1.inter-L2.inter)*(rhs.L2.slope-rhs.L1.slope)<(rhs.L1.inter-rhs.L2.inter)*(L2.slope-L1.slope);
    }
};
struct Machine
{
    LL day,price,resold,gene;
    bool operator < (const Machine& rhs) const {return day<rhs.day;}
}Mac[maxn];
LL dp[maxn],N,C,D;
set<Line> LS;
set<Point> PS;
bool check(Line L0,Line L1,Line L2)
{
    return (L0.inter-L2.inter)*(L1.slope-L0.slope)<=(L0.inter-L1.inter)*(L2.slope-L0.slope);
}
set<Point>::iterator del;
void Join(Line L)
{
    auto it3=LS.lower_bound(L);
    if(it3==LS.begin()){PS.insert(Point(L,*it3));}
    else
    {
        it3--;
        auto it2=it3;it3++;
        bool back=it3==LS.end()?0:1;
        auto it1=it2;
        if(it2!=LS.begin())
        {
            it2--;
            it1=it2;
            it2++;
        }
    
        if(it3!=LS.end() && check((*it2),L,(*it3))) return;
        for(;it2!=LS.begin();)
            if(check((*it1),(*it2),L)) 
            {
                PS.erase(Point(*it1,*it2));
                if(back)
                {
                    PS.erase(Point(*it2,*it3));
                    PS.insert(Point(*it1,*it3));
                }
                auto tmp=it2;it1--;it2--;
                LS.erase(tmp);
            }
            else break;
        PS.insert(Point(*it2,L));
    }
    it3=LS.lower_bound(L);
    if(it3!=LS.end())
    {
        it3++;
        auto it4=it3;it3--;
        bool front=it3==LS.begin()?0:1;
        auto it2=it3;
        if(front)
        {
            it3--;
            it2=it3;
            it3++;
        } 
        for(;it4!=LS.end();) if(check(L,(*it3),(*it4))) 
            {
                PS.erase(Point(*it3,*it4));
                if(front)
                {
                    PS.erase(Point(*it2,*it3));
                    PS.insert(Point(*it2,*it4));
                }
                auto tmp=it3;it3++;it4++;
                LS.erase(tmp);
            }
            else break;
        if(front)
        {
            PS.erase(Point(*it2,*it3));
            PS.insert(Point(*it2,L));
        }
            PS.insert(Point(L,*it3));
    }
    LS.insert(L);
}
LL getMax(LL x)
{
    if(PS.size()==0) return C;
    Line L1=Line(1,0);
    Line L2=Line(2,-x);
    Point P=Point(L1,L2);
    auto it=PS.lower_bound(P);
    if(it==PS.end()) it--;
    P=*it;
    return max(max(P.L1.getVal(x),P.L2.getVal(x)),C);
}
void solve(long long kase)
{
    sort(Mac+1,Mac+N+1);
    Mac[N+1]=(Machine){D+1,0,0,0};
    LS.clear();LS.insert(Line(0,C));dp[0]=C;
    PS.clear();
    for(LL i=1;i<=N+1;i++)
    {
        dp[i]=getMax(Mac[i].day);
        if(i!=N+1 && dp[i]>=Mac[i].price)
            Join(Line(Mac[i].gene,Mac[i].resold-Mac[i].price+dp[i]-(Mac[i].day+1)*Mac[i].gene));
        if(LS.size()!=PS.size()+1) return;
    }
    printf("Case %lld: %lld\n",kase,(long long)dp[N+1]);
}
int main()
{
    long long kase=0,NN,CC,DD;
    while(scanf("%lld%lld%lld",&NN,&CC,&DD)==3 && NN && CC && DD)
    {
        N=NN,C=CC,D=DD;
        for(long long i=1,a,b,c,d;i<=N;i++) {scanf("%lld%lld%lld%lld",&a,&b,&c,&d);Mac[i].day=a,Mac[i].price=b,Mac[i].resold=c,Mac[i].gene=d;}
        solve(++kase);
    }
}