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
種田君。。
