NOI2007 货币兑换 - CDQ分治斜率优化dp

斜率优化dp维护一个凸壳。如果\(x, y\)坐标都递增，可以用单调队列，如果只有\(x\)递增，可以在凸壳上二分斜率，如果\(x, y\)都不递增，则需要在凸包中插入，可以用平衡树或cdq分治维护。然而我不会平衡树，所以只好用cdq分治了。

题目

给定每天钱换A,B两种金券的汇率\(A_i, B_i\)，以及每天固定的钱换A,B两种券的比例\({A \over B} = Rate_i\)，卖出可以等比例卖出A,B两种券各自\(OP\%\)，求\(n\)天的最大收益，开始钱数为\(S\)。

\(n \leq 10^5\)

dp

题目提示我们，每次买入一定花完所有的钱，卖出一定卖出所有的金券。（既然有最优方案为什么不全用）

因此，设第\(i\)天的最大收益为\(f_i\)，为了方便推出斜率优化的方程，设\(f_i\)可以换成\(x_i\)的A劵和\(y_i\)的B劵。以下将\(Rate\)写成\(R\)。
\[x_i = f_i {R_i \over A_iR_i + B_i}\]
\[y_i = f_i {1 \over A_iR_i + B_i}\]

则有方程
\[f_i = \max\{f_{i-1}, \max\{x_jA_i + y_jB_i\}\}\]

暂时不考虑\(f_{i-1}\)，将后面的改成斜率的形式。

转移到\(f_i\)，\(f_j\) 比 \(f_k\)优：
\[x_jA_i + y_jB_i > x_kA_i + y_kB_i\]
\[(x_j-x_k)A_i > -(y_j-y_k)B_i\]
\[{{y_j-y_k}\over{x_j-x_k}} > -{A_i \over B_i}\]
注意不等式符号方向要改。

很明显\(x,y\)都是没有单调性的，无法直接用单调栈或队列建凸壳。

cdq分治

因为cdq分治可以将区间分成两块，然后统计前一块对后一块的贡献，所以可以对前一块的\(x\)进行排序，就可以建凸壳，进行后半部分的转移了。

注意三种顺序：

1. 分治前先按\(-{A_i \over B_i}\)排序，保证后半部分查询凸壳是有序的，这样可以用一个指针扫描，否则二分多一个log。
2. 分成两块前，按\(pos\)分组，\(pos \leq mid\)放在前一块，\(pos > mid\)放在后一块，保证用编号小的更新编号大的。同时，这样可以保证分治到叶子是按编号顺序的，，即对于叶子\(l = r = pos\)，分治到叶子时这个节点就已经全部更新完了，这样就可以处理\(f_i = \max\{f_i, f_{i-1}\}\)。
3. 最后按\(x\)归并，方便建上凸凸壳。

不要把斜率改成乘法的形式，因为负数比较多，改成乘法需要注意不等式方向，直接用斜率比较方便。

定义\(slope(i, j)\)为\(i\)到\(j\)的斜率（\(i, j\)是分治节点编号），找到凸壳中第一个\(i\)满足\(slope(S_i, S_{i+1})<-{A_i \over B_i}\)的就是最优转移点了，注意如果两个\(x\)相等，返回极大斜率就可以了，可以不用\(eps\)判断，直接判等，保证除数不为\(0\)即可。

分治的过程伪代码

1. if(l == r) 用f[i-1]更新f[i]，计算x,y exit
2. cdq(l, mid)
3. 单调栈对[l, mid]建凸壳
4. 按\(-{A_i \over B_i}\)顺序扫描，转移
5. cdq(mid+1, r)
6. 按x归并

Code

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100005;
const double eps = 1e-9, inf = 1e9;
struct val{
    int p; double x, y;
}q[N], tmp[N];
double f[N], A[N], B[N], R[N];
int s[N];
bool cmp(val a, val b){return -(A[a.p] / B[a.p]) > -(A[b.p] / B[b.p]);}
double slope(int x, int y){
    if(q[x].x == q[y].x) return inf;
    return (q[y].y - q[x].y) / (q[y].x - q[x].x);
}

void cdq(int l, int r){
    if(l == r){ //完成对节点的处理
        f[l] = max(f[l], f[l-1]);
        q[l].x = f[l] / (A[l] * R[l] + B[l]) * R[l];
        q[l].y = f[l] / (A[l] * R[l] + B[l]);
        return ;
    }
    int mid = (l + r) >> 1, lp = l, rp = mid + 1, tp = l;
    for(int i=l; i<=r; i++) //分组
        if(q[i].p <= mid) tmp[lp++] = q[i];
        else tmp[rp++] = q[i];
    for(int i=l; i<=r; i++) q[i] = tmp[i];
    cdq(l, mid);
    int t = 0, p = 1;
    for(int i=l; i<=mid; i++){ //建凸壳
        while(t > 1 && slope(s[t], i) > slope(s[t-1], s[t])) --t;
        s[++t] = i;
    }
    for(int i=mid+1; i<=r; i++){ //转移
        while(p < t && slope(s[p], s[p+1]) > -A[q[i].p] / B[q[i].p]) ++p;
        f[q[i].p] = max(f[q[i].p], q[s[p]].x * A[q[i].p] + q[s[p]].y * B[q[i].p]);
    }
    cdq(mid+1, r);
    lp = l; rp = mid + 1; tp = l;
    while(lp <= mid && rp <= r) //归并
        if(q[lp].x < q[rp].x) tmp[tp++] = q[lp++];
        else tmp[tp++] = q[rp++];
    while(lp <= mid) tmp[tp++] = q[lp++];
    while(rp <= r) tmp[tp++] = q[rp++];
    for(int i=l; i<=r; i++) q[i] = tmp[i];
}

int main(){
    int n; double s;
    scanf("%d%lf", &n, &s);
    for(int i=1; i<=n; i++){
        scanf("%lf%lf%lf", &A[i], &B[i], &R[i]);
        q[i].p = i; //pos
        q[i].x = s / (A[q[i].p] * R[q[i].p] + B[q[i].p]) * R[q[i].p];
        q[i].y = s / (A[q[i].p] * R[q[i].p] + B[q[i].p]);
        f[i] = s; //用s初始化
    }
    sort(q+1, q+1+n, cmp);
    cdq(1, n);
    printf("%.3lf\n", f[n]);
    return 0;
}

NOI2007 货币兑换 - CDQ分治斜率优化dp

原文：https://www.cnblogs.com/RiverHamster/p/cdq-slopedp.html