BZOJ 1492: [NOI2007]货币兑换Cash – [斜率优化/CDQ分治]

题目传送门(BZOJ)
>原文链接<

题解 :

首先要注意到题目中所说的
“必然存在一种最优的买卖方案满足:
每次买进操作使用完所有的人民币;
每次卖出操作卖出所有的金券。”

当然,上面那个贪心的性质从感性上很好理解,理性的证明我没有!

状态 :

  • $F[i]$ 代表到第$i$天的最大利润,

  • $X[i]$表示在第$i$天最多有几张$A$卷,

  • $Y[i]$表示在第$i$天最多有几张$B$卷。

基础转移 :

  • $F[i] = \max(F[i-1], \max{X[j]\times A[i]+Y[j]\times B[i]})$

  • $Y[i] = F[i]/(A[i]\times Rate[i]+B[i])$

  • $X[i] = Y[i]\times Rate[i]$

不考虑F[i-1]来的转移,我们可以把式子化成这样 :

F[i]/A[i] = X[j]+Y[j]\times(B[i]/A[i])

可以把Y[j]当作斜率K,把(B[i]/A[i])当作x。做斜率优化。

但这当然是布星的,因为Y[j]或是(B[i]/A[i]) 都不单调

那么我们就让它单调,首先(B[i]/A[i])是可以直接排序的。

那么对另一维的处理方法就呼之欲出了 —— CDQ分治。

其实对于F[i]的更新,我们只要拿出它前面的所有直线就可以了,由于所有(B[i]/A[i])在它前面的都被排到前面去了,所以我们可以不用考虑这个。

对于分治的每段区间,我们先处理出它左区间的所有直线,然后维护凸包给它右区间的F[x]更新,再递归它右区间。归并排序返回到上一层

至于维护最优斜率,和普通的斜率优化都差不多,如果还有不明白,请看代码。 CDQ分治的意义是拿出所有单调的直线,同理可以用 Splay 维护凸包,但是实在是太难写了。

#include 
#define F2 double
#include 
using namespace std;
const int N = 101010;
#define getY(i, j) (K[j]*cur[i]+X[j])
F2 A[N], B[N], X[N], Y[N], f[N], R[N], K[N], cur[N];
int n, t[N], tmp[N], S[N]; 
inline bool cmp(int x, int y) {return cur[x] < cur[y];}
inline bool Cmp(int c1, int c2, int c3) {
    return (Y[c2]-Y[c3])*(X[c1]-X[c2]) <= (Y[c1]-Y[c2])*(X[c2]-X[c3]);
}
void getAns(int l, int r) {
    if(l == r) {
        f[l] = max(f[l], f[l-1]);
        Y[l] = f[l]/(R[l]*A[l]+B[l]);
        X[l] = Y[l]*R[l];
        K[l] = Y[l];
        return ;  
    }
    int mid = (l+r) >> 1;
    int p1 = l, p2 = mid+1;
    for(int i = l; i <= r; i ++ ) {
        if(t[i] <= mid)  tmp[p1 ++ ] = t[i];
        else tmp[p2 ++ ] = t[i];
    }
    for(int i = l; i <= r; i ++ ) t[i] = tmp[i];
    getAns(l, mid); *S = 0;
    for(int i = l; i <= mid; i ++ ) {
        while(*S > 1 && Cmp(S[*S-1], S[*S], t[i])) -- *S;
        S[++*S] = t[i];
    }
    for(int j = 1, i = mid+1; i <= r; i ++ ) {
        while(j < *S && getY(t[i], S[j+1]) >= getY(t[i], S[j])) j ++ ;
        f[t[i]] = max(f[t[i]], getY(t[i], S[j])*A[t[i]]);
    }
    getAns(mid+1, r);
    int p3 = l; p1 = l, p2 = mid+1;
    while(p1 <= mid && p2 <= r) {
        if(K[t[p1]] > K[t[p2]]) tmp[p3 ++ ] = t[p2 ++ ];
        else tmp[p3 ++ ] = t[p1 ++ ];
    }
    while(p1 <= mid) tmp[p3 ++ ] = t[p1 ++ ];
    while(p2 <= r) tmp[p3 ++ ] = t[p2 ++ ];
    for(int i = l; i <= r; i ++ ) t[i] = tmp[i];
}
int main() {
    scanf("%d%lf", &n, &f[0]);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%lf%lf%lf", &A[i], &B[i], &R[i]);
        t[i] = i, cur[i] = B[i]/A[i];
    }
    sort(t+1, t+n+1, cmp);
    getAns(1, n);
    printf("%.3f\n", f[n]);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注