题目传送门(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 <cstdio>#define F2 double#include <algorithm>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]);}