解析
根据贪心容易想到每天要不全部买入要不然全部卖出(因为如果可以赚那为什么不多赚一点)
那么就可以得到一个转移方程:(f[i]) 代表到第 (i) 天把所有金券都卖掉可以得到的钱最多为多少。
考虑转移时可以从任意一天买进在今天卖出,可以得到下面的方程:(f[i]=max_{0<j<i}frac{f_j imes a_i imes r_j+f_j imes b_i}{a_j imes r_j+b_j})
今天还可以不卖也不卖,(f[i]=f[i-1])。
故我们可以写出一个 (O(n^2)) 的代码:
f[0]=s;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
f[i] = max(f[i], (f[j]*a[i]*rate[j]+f[j]*b[i])/(a[j]*rate[j]+b[j])
}
f[i]=max(f[i],f[i-1]);
}
考虑优化掉它,因为 (val(i,j)) 有 (i) 和 (j) 的乘法项所以不能用单调队列优化,得斜率优化。可以先提出来一个 (g_j=frac{f_j}{a_j imes r_j+b_j})。
先化成斜率式:(frac{f_i}{a_i}-frac{b_i}{a_i}g_j=g_jr_j),然后我们发现无论是斜率还是决策点都没有单调性,所以用平衡树/cdq来实现。
我是用cdq来写的,不会的看这里。
#include <bits/stdc++.h>
using namespace std;
const double inf = 1e9;
const int MAXN = 100005;
struct node{
double k, g;
int id;
friend bool operator < (node a, node b) {
return a.k > b.k;
}
}p[MAXN], tmp[MAXN];
int n;
double s, f[MAXN], a[MAXN], b[MAXN], rate[MAXN];
int q[MAXN], head, tail;
double X(int i) { return p[i].g; }
double Y(int i) { return p[i].g * rate[p[i].id]; };
double slope(int i, int j) { return X(i) == X(j) ? (Y(i) > Y(j) ? inf : -inf) : (Y(i) - Y(j)) / (X(i) - X(j)); }
bool cmp(int aa, int bb) {
return X(aa) != X(bb) ? X(aa) < X(bb) : Y(aa) < Y(bb);
}
void cdq(int l, int r) {
if (l == r) {//递归到最下曾时,dp值已经算出,那就可以算这个点的 X,Y 值了
f[p[l].id] = max(f[p[l].id], f[p[l].id - 1]);
p[l].g = f[p[l].id] / (a[p[l].id] * rate[p[l].id] + b[p[l].id]);
return;
}
int mid = (l + r) >> 1, h1 = l, h2 = mid + 1;
for (int i = l; i <= r; i++) p[i].id <= mid ? tmp[h1++] = p[i] : tmp[h2++] = p[i];
for (int i = l; i <= r; i++) p[i] = tmp[i];
//根据下标分成两个部分使得前半部分的下标都是小于后半部分的下标
//此时[l,r]区间内的斜率可能不单调,但是[l,mid]和[mid+1,r]的斜率是单调的
cdq(l, mid);//递归处理前半部分
//归并排序后保证决策点的横坐标是单调的
//把前半部分的点建成凸包
head = 1, tail = 0;
for (int i = l; i <= mid; i++) {
while (head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i)) tail--;
q[++tail] = i;
}
for (int i = mid + 1; i <= r; i++) {
while (head < tail && slope(q[head], q[head + 1]) >= p[i].k) head++;
f[p[i].id] = max(f[p[i].id], (-p[i].k + rate[p[q[head]].id]) * p[q[head]].g * a[p[i].id]);
}
cdq(mid + 1, r);
h1 = l, h2 = mid + 1;
int top = 0;
while (h1 <= mid && h2 <= r) {
if (cmp(h1, h2)) tmp[++top] = p[h1++];
else tmp[++top] = p[h2++];
}
while (h1 <= mid) tmp[++top] = p[h1++];
while (h2 <= r) tmp[++top] = p[h2++];
for (int i = 1; i <= top; i++) p[l + i - 1] = 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], &rate[i]);
p[i].k = -b[i] / a[i];
p[i].id = i;
}
//先按照斜率排序
sort(p + 1, p + 1 + n);
cdq(1, n);
printf("%.3lf", f[n]);
return 0;
}