题解 P4027 【[NOI2007]货币兑换】

RiverHamster · 2019-08-02 22:31:32 · 题解

下面的cdq分治写法讲的都比较简单，弄得蒟蒻写了一天，发个题解总结一下。

在我的blog阅读

dp

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

因此，设第i天的最大收益为f_i，为了方便推出斜率优化的方程，设f_i可以换成x_i的A劵和y_i的B劵。以下将Rate写成R。

则有方程

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

转移到f_i，f_j 比 f_k优：

注意不等式符号方向要改。

很明显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;
}