# BZOJ 1492. [NOI2007]貨幣兌換Cash

### Analysis:

##### 演算法一：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] = 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]);
}
```

```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將被刪除）