BZOJ 1492. [NOI2007]貨幣兌換Cash

Brief description:

Analysis:

演算法一:cdq 分治

隨著科技的進步我們已經知道可以使用 cdq 分治來解決這類問題了。。。


//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
DB A[N], B[N], R[N], f[N];
int n;

#define y(i) (f[i] / (R[i] * A[i] + B[i]))
#define x(i) (R[i] * y(i))

bool cmp_k(int i, int j){
    return A[i]*B[j] < A[j]*B[i];
}

void cdq(int l, int r){
    if (l + 1 == r){
        checkMax(f[r], f[l]);
    }
    else{
        int m = l + r >> 1; cdq(l, m);
        static Po P[N], C[N]; int pn = 0, cn = 0;
        FOR(i, l, m) P[pn++] = Po(x(i), y(i)); sort(P, P+pn);

        REP(i, pn){
            while (cn > 1 && dett(C[cn-1], C[cn], P[i]) >= 0) --cn;
            C[++cn] = P[i];
        }

        static int Q[N]; int qn = 0;
        FOR(i, m, r) Q[qn++] = i; sort(Q, Q+qn, cmp_k);

#define eval(c) (A[i]*C.x + B[i]*C.y)

        int c = 1; REP(q, qn){
            int i = Q[q]; while (c < cn && eval(c) < eval(c+1)) ++c;
            checkMax(f[i], eval(c));
        }

        cdq(m, r);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    freopen("cash7.in", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); RF(f[0]); REP(i, n) RF(A[i], B[i], R[i]);
    cdq(0, n); OT(f[n]);
}

https://gist.github.com/lychees/6f7e2fb392c24da5bd16#file-cdq_o-nlog2n-cpp


//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
DB A[N], B[N], R[N], f[N];
int n;

#define y(i) (f[i] / (R[i] * A[i] + B[i]))
#define x(i) (R[i] * y(i))

bool cmp_k(int i, int j){
    return A[i]*B[j] < A[j]*B[i];
}

int Q[N]; Po C[N], P[N];

void cdq(int l, int r){
    if (l + 1 == r){
        checkMax(f[r], f[l]);
        P[l] = Po(x(l), y(l));
    }
    else{
        int m = l + r >> 1;

        static int tmp[N]; int tl = l, tr = m;
        FOR(i, l, r) if (Q[i] < m) tmp[tl++] = Q[i]; else tmp[tr++] = Q[i];
        memcpy(Q+l, tmp+l, sizeof(int) * (r-l));

        VP Pl, Pr; cdq(l, m);

        int cn = 0; FOR(i, l, m){
            while (cn > 1 && dett(C[cn-1], C[cn], P[i]) >= 0) --cn;
            C[++cn] = P[i];
        }

#define eval(c) (A[i]*C.x + B[i]*C.y)

        int c = 1; FOR(q, m, r){
            int i = Q[q]; while (c < cn && eval(c) < eval(c+1)) ++c;
            checkMax(f[i], eval(c));
        }

        cdq(m, r);

        static Po tmpP[N]; merge(P+l, P+m, P+m, P+r, tmpP);
        memcpy(P+l, tmpP, sizeof(Po)*(r-l));
    }
}


int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    freopen("cash7.in", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); RF(f[0]); REP(i, n) RF(A[i], B[i], R[i]), Q[i] = i; sort(Q, Q+n, cmp_k);
    cdq(0, n); OT(f[n]);
}

https://gist.github.com/lychees/6f7e2fb392c24da5bd16#file-cdq_o-nlogn-cpp

演算法二:平衡樹維護凸殼

。。。看來還是賈教(Oimaster)解釋的最清楚。。0 w0。

根據提示內容,我們就可以得到一個動態規劃演算法:用f[i]表示到第i天為止能得到的最多錢數。根據f[i],我們可以得到如果第i天賣出金券的話,A券和B券各有多少張(我們設為X[i]和Y[i])。則轉移方程為:
f[i] = max( f[i-1], max{ X[j]*a[i] + Y[j]*b[i] | j <= i}) 邊界條件為f[1]=s。 其中X[i]和Y[i]可以根據f[i]得出,具體就不講了。

const int N = 109;
DB A[N], B[N], R[N], f[N];
int n; DB ans;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

	RD(n); RF(f[0]); REP_1(i, n) RF(A[i], B[i], R[i]);

#define b(i) (f[i] / (R[i] * A[i] + B[i]))
#define a(i) (R[i] * b(i))

    REP_1(i, n){
        f[i] = f[i-1];
        REP(j, i) checkMax(f[i], a(j)*A[i] + b(j)*B[i]);
    }

	OT(f[n]);
}

這個動態規劃顯然是1D/1D動態規劃,普通做法的時間複雜度為O(n^2),對於100000的數據顯然是會超時的,所以還要優化。
我們把所有的X[i]和Y[i]抽象成坐標系中的點,即X[i]為橫坐標,Y[i]為縱坐標。
然後我們令P=a[i]*x+b[i]*y,即轉移方程中的(X[j]*a[i]+Y[j]*b[i])。變形可得y=(-a[i]/b[i])*x+P/b[i],即有一條斜率一定的直線,並且經過某個點(x,y),然後要最大化截距。對於這個問題,我們可以想像成有一條斜率為(-a[i]/b[i])的直線從無窮遠的地方向下,第一個碰到的點即為最優解。那麼就可以得到以下結論:
如果點(X[i],Y[i])為某次的最優決策,那麼顯然這個點是在所有點的凸殼上的,如下圖中的C點不可能為最優的決策點。

原因很簡單,如果有一條斜率一定直線從上向下平移過來,必定先碰到點A或點B,不可能先碰到點C。
因此我們維護一個決策序列,這個決策序列中的點即為凸殼上的點,然後我們按橫坐標將這些點排序,則縱坐標也就有序,並且相鄰兩個點的連線的斜率單調遞減。
對於一條斜率一定的直線,其最優解的點必然是這樣的:

即如果這條直線的斜率為k,最優決策點與其相鄰兩點連線的斜率分別為k1和k2,則滿足k1>=k>=k2。

因此現在我們的任務是怎樣高效地維護這個決策點序列,顯然平衡樹可以很好的做到這點。我們將這些點按照橫坐標的大小建一棵平衡樹,那麼縱坐標也有序,然後每新算出來一個f[i],算出與其對應的X[i]與Y[i],先按橫坐標找到這個點的插入位置。然後我們判斷這個點是否應該保留,如果出現第一幅圖中的情況,那麼這個點無需插入,否則將這個點插入平衡樹中。下面就是維護這個凸殼,我們從這個點開始,分別向左和向右找到第一個滿足凸殼的兩個點,將中間的點刪除。對於取得f[i]最優決策,因為斜率單調減,因此我們可以二分(即判斷這個點是在左子樹中還是右子樹中)。其中凸殼維護過程如下圖所示

struct node{
    static node*NIL,*root; // 哨兵、根結點 .. .
    node*c[2],*p; PDD o; DB k[2]; // 孩子、父親、坐標、斜率。。
}
.. .
    inline void clean(int d){
        for (node*x=neighbor(d);x!=NIL;x=neighbor(d)){ //x->o.se < o.se ^ d
            if (x->splay(this)->k[d] < get_k(o, x->o) ^ d) setc(d, x->c[d]);
            else break;
        }
    }

    inline void clean(){
        clean(0), clean(1);
    }

    inline node*fix(){
        splay(); node*a = pred(),*b = succ();
        k[0] = a == NIL ? +OO : get_k(o, a->o);
        k[1] = b == NIL ? -OO : get_k(o, b->o);
        if (k[0] < k[1]){
            root = a->splay(this), a->p = NIL, a->setr(r);
        }
        else {
            clean(), a = pred(), b = succ();
            k[0] = a == NIL ? +OO : a->k[1] = get_k(o, a->o);
            k[1] = b == NIL ? -OO : b->k[0] = get_k(o, b->o);
        }
    }
.. .
// x->k[0] > k > x->k[1]
node*Find(DB k){
    for (node*x=root;;){
        if (x->k[0]<k) x=lx; else if (k<x->k[1]) x=rx;
        else return x;
    }
}

void Insert(node*z){
    node*x=root,*y=NIL; for(;x!=NIL;y=x,x = x->c[z->o>x->o]);
    if (y == NIL) root = z; else y->setc(z->o>y->o, z);
    z->fix();
}

(我們現在插入點P,則點B和點C將被刪除)
最後討論平衡樹的選擇,這題實際上用哪種平衡樹都是可以的,但最方便的無疑是Splay,如果我們選擇插入點P,那麼我們將點P旋轉到根節點,然後找到P的前驅(即左子樹中最大的),判斷是否刪除,如果刪除,那麼繼續上述過程,然後再對右子樹進行維護。最終複雜度O(nlogn),完全可以對付100000的數據。
最後想說的是,這題編程中的細節比較多,如遇到橫坐標相同的點怎麼辦,甚至橫縱坐標都相同的點怎麼辦,所以編程之前要想清楚一些細節問題。

Splay 維護凸殼。。(斜率。。600ms +-
Splay 維護凸殼。。(叉積。。550ms–

External link:

http://www.lydsy.com/JudgeOnline/problem.php?id=1492
http://hi.baidu.com/oimaster/item/d8041f4a865444ee1f19bc43
種田君。。