Description：

有 $n$ 天，第 $i$ 天 $A$ 券价格为 $a[i]$ ， $B$ 券价格为 $b[i]$ ，第 $i$ 天可以同时卖出 $w\%$ 的 $A$ 券和 $B$ 券，或者按 $rate[i]$ 的比例买入价值不超过当前拥有钱数的两种金券，或者什么都不做，最大化最后手中的人民币。

提示：一定存在一种方案每次用手中的钱全部买入金券或者全部卖出手中所有金券或者什么都不做。

$1\le n \le 10^5$

Solution：

提示都说了。不难得到 $DP$ 方程：

设 $x[i]$ 表示第 $i$ 天所能得到的最多 $A$ 券数量， $y[i]$ 表示第 $i$ 天所能得到的最多 $B$ 券数量，则：

$rate[i]\times y[i]\times a[i]+y[i]\times b[i]=f[i]$ ， $y[i]=\frac{f[i]}{a[i]\times rate[i]+b[i]}$ ， $x[i]=\frac{f[i]\times rate[i]}{a[i]\times rate[i]+b[i]}$ 。

$f[i]=max(x[j]\times a[i]+y[j]\times b[i],f[i-1])$ 。

先不管后面的 $f[i-1]$ ，得到了 $f[i]=x[j]\times a[i]+y[j]\times b[i]$ 。

变一下型，得： $y[j]=-\frac{a[i]}{b[i]}x[j]+\frac{f[i]}{b[i]}$ 。

斜率优化，维护上凸壳， $x$ ， $k$ 都不单调，用 $splay$ 维护上凸壳 $+$ 二分或 $cdq$ 分治。

Code：

$splay$ ：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

#define INF 0x3f3f3f3f

double f;

double x(double a,double b,double rate,double f){return f * rate / (rate * a + b);}

double y(double a,double b,double rate,double f){return f / (rate * a + b);}

int tot = 0;

struct node

{

    int c[2],fa;

    double x,y;

}t[MAXN];

int ptr = 0;

int newnode(){return ++ptr;}

int root = 0;

int createnode(int fa,double x,double y){++tot;int k = newnode();t[k].x = x;t[k].y = y;t[k].fa = fa;return k;}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

    int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

    connect(t[x].c[fx ^ 1],y,fx);

    connect(y,x,fx ^ 1);

    connect(x,z,fy);

    return;

}

void splay(int x,int &k)

{

    int to = t[k].fa;

    while(t[x].fa != to)

    {

        int y = t[x].fa;

        if(t[y].fa == to){rotate(x);break;}

        if(id(x) == id(y)){rotate(y);rotate(x);}

        else{rotate(x);rotate(x);}

    }

    k = x;

    return;

}

int pre(int p)

{

    splay(p,root);

    int k = t[root].c[0];if(k == 0)return INF;

    while(t[k].c[1] != 0)k = t[k].c[1];

    return k;

}

int nxt(int p)

{

    splay(p,root);

    int k = t[root].c[1];if(k == 0)return INF;

    while(t[k].c[0] != 0)k = t[k].c[0];

    return k;

}

void remove(int k)

{

    --tot;

    splay(k,root);

    if(t[k].c[0] == 0 && t[k].c[1] == 0)

    {

        root = 0;

        return;

    }

    if(t[k].c[0] == 0 || t[k].c[1] == 0)

    {

        int s = t[k].c[0] + t[k].c[1];

        root = s;

        t[s].fa = 0;

        return;

    }

    int r = nxt(k);splay(r,t[k].c[1]);

    connect(t[k].c[0],r,0);

    t[r].fa = 0;root = r;

    return;

}

double slope(int a,int b){return (t[a].y - t[b].y) / (t[a].x - t[b].x);}

void maintain(int k)

{

    splay(k,root);

    if(pre(k) != INF && nxt(k) != INF)

    {

        int l = pre(k),r = nxt(k);

        double ly = (t[r].y - t[l].y) / (t[r].x - t[l].x) * (t[k].x - t[l].x) + t[l].y;

        if(t[k].y <= ly)

        {

            remove(k);

            return;

        }

    }

    while(true)

    {

        int l1 = pre(k);if(l1 == INF)break;

        int l2 = pre(l1);if(l2 == INF)break;

        if(slope(k,l1) >= slope(l1,l2))remove(l1);

        else break;

    }

    while(true)

    {

        int r1 = nxt(k);if(r1 == INF)break;

        int r2 = nxt(r1);if(r2 == INF)break;

        if(slope(k,r1) <= slope(r1,r2))remove(r1);

        else break;

    }

    return;

}

void insert(double x,double y)

{

    if(root == 0)

    {

        root = createnode(0,x,y);

        return;

    }

    int k = root;

    while(true)

    {

        if(x < t[k].x)

        {

            if(t[k].c[0] == 0){t[k].c[0] = createnode(k,x,y);k = t[k].c[0];break;}

            k = t[k].c[0];

        }

        else if(x > t[k].x)

        {

            if(t[k].c[1] == 0){t[k].c[1] = createnode(k,x,y);k = t[k].c[1];break;}

            k = t[k].c[1];

        }

        else{t[k].y = max(t[k].y,y);break;}

    }

    maintain(k);

    return;

}

double query(double a,double b)

{

    double k = -(a / b);

    int p = root;

    double ans = 0;

    while(true)

    {

        if(p == 0)break;

        int i = t[p].c[1];

        if(i == 0)

        {

            ans = max(ans,t[p].x * a + t[p].y * b);

            p = t[p].c[0];

            continue;	

        }

        while(t[i].c[0] != 0)i = t[i].c[0];

        if(slope(p,i) >= k)p = t[p].c[1];

        else

        {

            ans = max(ans,t[p].x * a + t[p].y * b);

            p = t[p].c[0];

        }

    }

    return ans;

}

int main()

{

    scanf("%d%lf",&n,&f);

    double a,b,rate;

    for(int i = 1;i <= n;++i)

    {

        scanf("%lf%lf%lf",&a,&b,&rate);

        f = max(f,query(a,b));

        insert(x(a,b,rate,f),y(a,b,rate,f));

    }

    printf("%.3f\n",f);

    return 0;

}

$cdq$ 分治（只有 $80$ 分，似乎卡精度）

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

double f[MAXN];

struct day

{

    double a,b,rate;

    int id;

    day(){a = b = rate = 0.0;id = 0;}

}d[MAXN];

inline double x(day t){return f[t.id] / (t.a * t.rate + t.b) * t.rate;}

inline double y(day t){return f[t.id] / (t.a * t.rate + t.b);}

int s[MAXN],top;

inline double slope(day a1,day a2){return (y(a2) - y(a1)) / (x(a2) - x(a1));}

bool cmp_x(day a1,day a2){return x(a1) < x(a2);}

inline double k(day t){return -(t.a / t.b);}

bool cmp_k(day a1,day a2){return k(a1) < k(a2);}

bool cmp_id(day a1,day a2){return a1.id < a2.id;}

void cdq(int l,int r)

{

    if(l == r){f[l] = max(f[l],f[l - 1]);return;}

    int mid = (l + r) / 2;

    cdq(l,mid);

    sort(d + l,d + mid + 1,cmp_x);

    top = 0;

    for(int i = l;i <= mid;++i)

    {

        while(top >= 2 && slope(d[i],d[s[top]]) > slope(d[s[top]],d[s[top - 1]]))--top;

        s[++top] = i;

    }

    sort(d + mid + 1,d + r + 1,cmp_k);

    for(int i = mid + 1;i <= r;++i)

    {

        while(top >= 2 && k(d[i]) > slope(d[s[top]],d[s[top - 1]])){--top;}

        day t = d[s[top]];

        f[d[i].id] = max(f[d[i].id],x(t) * d[i].a + y(t) * d[i].b);

    }

    sort(d + mid + 1,d + r + 1,cmp_id);

    cdq(mid + 1,r);

    return;

}

int main()

{

    memset(f,0,sizeof(f));

    scanf("%d%lf",&n,&f[0]);

    for(int i = 1;i <= n;++i)

    {

        d[i].id = i;

        scanf("%lf%lf%lf",&d[i].a,&d[i].b,&d[i].rate);

    }

    cdq(1,n);

    printf("%.3lf\n",f[n]);

    return 0;

}