题意
一家金券交易所只发行交易两种金券:A券和B券。
我们记录第(K)天中A券和B券的价值分别为(A_K)和(B_K)(元/单位金券)
交易所提供两种操作：
a)卖出金券:顾客将(OP\%)的A券和(OP\%)的B券以当时的价值兑换为人民币;
b)买入金券:顾客支付(IP)元人民币，交易所将会兑换给用户总价值为(IP)
的金券，并满足提供给顾客的A券和B券的比例在第K天恰好为(Rate_K)。
给出未来(N)天内的(A_K)，(B_K)和(R_K)，
开始时拥有(S)元钱，求出(N)天后最多能够获得多少元钱。
必然存在一种最优的买卖方案满足：
每次买进操作使用完所有的人民币；
每次卖出操作卖出所有的金券。
数据范围
[N≤10^5,0<A_K,B_Kle10,0<R_Kle100
]
sol
既然题面都这么友善那我们就照着题目来吧
先分析一下买进和卖出操作:
买进:使用(IP)元，买入(frac{R_KIP}{A_KR_K+B_K})张A券和(frac{IP}{A_KR_K+B_K})张B券
卖出:卖出(F_A)张A券和(F_B)张B券，获得收入(F_AA_K+F_BB_K)元
在这种极端的操作下，我们发现:
购买方案一定由多个不相交的买入——卖出序列构成的
那么我们考虑一次买入——卖出操作，在第(K)天买入，第(K')天卖出;
买进:使用(S)元，买入(frac{R_KS}{A_KR_K+B_K})张A券和(frac{S}{A_KR_K+B_K})张B券
卖出:卖出(frac{R_KS}{A_KR_K+B_K})张A券和(frac{S}{A_KR_K+B_K})张B券，
获得收入((A_{K'}frac{R_KS}{A_KR_K+B_K}+B_{K'}frac{S}{A_KR_K+B_K}))元
两者之比为(frac{A_{K'}R_K+B_{K'}}{A_KR_K+B_K})
于是我们考虑建立DP方程:
设(f[i])为前(i)天所能获得的最大比值，(f[1]=1)，有
[f[i]=max{f[i-1],max_{j=1}^{i}frac{f[j] imes(A_iR_j+B_i)}{A_jR_j+B_j}}
]
最后答案为(max_{i=1}^{n}f[i]),这时复杂度是(O(n^2))的。
update 10.15:感谢@mona指出了本蒟蒻dp方程和最后答案的错误，之前这里写的是(f[n])
考虑斜率优化，
[f[i]=B_i imes max_{j=1}^{i}[frac{f[j] imes(R_j imesfrac{A_i}{B_i}+1)}{A_jR_j+B_j}]
]
[=B_i imes max_{j=1}^{i}(frac{A_i}{B_i} imesfrac{f[j]R_j}{A_jR_j+B_j}+frac{f[j]}{A_jR_j+B_j})
]
插点((frac{f[j]R_j}{A_jR_j+B_j},frac{f[j]}{A_jR_j+B_j}))，询问(k_i=-frac{A_i}{B_i})即可?
然而(x_j=frac{f[j]R_j}{A_jR_j+B_j})并不是单增的，因此我们要考虑如何维护这个上凸包
那么...本篇题解的重点
Splay动态维护上凸包
由于Splay可以把横坐标排序，那么我们只需要动态处理纵坐标即可
每个点最多进入Splay一次，被弹出一次，两次时间都是(O(logn)),
所以Splay维护的总复杂度就是(O(nlogn))
查询凸包值的时候，在Splay上二分即可，总复杂度是(O(nlog^2n))
那么这道题实际是一道数据结构题
调了(2.5h)终于成功
似乎有还有一种CDQ分治的做法，但由于本人太弱因此只能用Splay
Extra:CDQ分治篇
update 9.19:终于学了CDQ分治，补完本篇
因为(CDQ)分治可以消除一维偏序的影响,所以我们用其保证(x)单调即可
因为序列(DP)是从前往后进行的，因此分治的步骤和传统的(CDQ)有些不同
其实这已经有点类似于线段树分治了..
Code
这里是(Splay)的代码
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define RG register
#define il inline
#define update(i) (sz[i]=sz[s[0][i]]+sz[s[1][i]]+1)
#define isr(i) (s[1][fa[i]]==i)
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-9;
const int mod=1e8;
const int N=100010;
const int inf=2147483647;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
ll n,S,rt,cnt;dd a[N],b[N],r[N],f[N],x[N],y[N];
int fa[N],s[2][N],sz[N];
il void print(int);
il void rot(int i){
RG int j=fa[i],k=fa[j];
RG bool b=isr(i);
if(k)s[isr(j)][k]=i;fa[i]=k;
if(j)s[b][j]=s[!b][i];if(s[!b][i])fa[s[!b][i]]=j;
s[!b][i]=j;fa[j]=i;
update(j);
}
il void splay(int i,int a){
if(!a)rt=i;
for(RG int j=fa[i];j!=a;rot(i),j=fa[i])
if(fa[j]!=a)isr(i)^isr(j)?rot(i):rot(j);
update(i);
}
il dd calc(int i,int j){
if(abs(x[i]-x[j])<=eps)return inf;
return (y[i]-y[j])/(x[i]-x[j]);
}
il void run_pop(int i){
RG int nxt=0,lst=0,lstt,nxtt;
splay(i,0);nxt=s[1][i];lst=s[0][i];
while(s[0][nxt])nxt=s[0][nxt];
while(s[1][lst])lst=s[1][lst];
if(lst)splay(lst,i);
while(s[0][lst]){
lstt=s[0][lst];
while(s[1][lstt])lstt=s[1][lstt];
splay(lstt,lst);
if(calc(lstt,lst)>calc(lst,i))break;
fa[lst]=s[0][lst]=s[1][lst]=0;
s[0][i]=lstt;fa[lstt]=i;lst=lstt;
update(i);splay(i,0);splay(lst,i);
}
splay(i,0);
if(nxt)splay(nxt,i);
while(s[1][nxt]){
nxtt=s[1][nxt];
while(s[0][nxtt])nxtt=s[0][nxtt];
splay(nxtt,nxt);
if(calc(i,nxt)>calc(nxt,nxtt))break;
fa[nxt]=s[0][nxt]=s[1][nxt]=0;
s[1][i]=nxtt;fa[nxtt]=i;nxt=nxtt;
update(i);splay(i,0);splay(nxt,i);
}
}
il void insert(dd rx,dd ry){
RG int i=rt,ff=0,nxt=0,lst=0;
while(i){
ff=i;
if(abs(rx-x[i])<=eps){
if(ry>y[i]){y[i]=ry;run_pop(i);}
return;
}
if(rx<x[i]){nxt=i;i=s[0][i];}
else if(rx>x[i]){lst=i;i=s[1][i];}
}
if(lst&&nxt&&calc(lst,i)<calc(i,nxt))return;
i=++cnt;if(i==1)rt=i;
if(ff)s[x[ff]<rx][ff]=i;fa[i]=ff;
x[i]=rx;y[i]=ry;
run_pop(i);
}
il void kth(int k){
RG int i=rt;
while(1){
if(k<=sz[s[0][i]])i=s[0][i];
else if(sz[s[0][i]]+1==k)break;
else k-=sz[s[0][i]]+1,i=s[1][i];
}
splay(i,0);
}
il ll check(ll mid,dd k,dd &ans){
kth(mid);RG int i=rt,nxt=s[1][i],lst=s[0][i];
while(s[0][nxt])nxt=s[0][nxt];
while(s[1][lst])lst=s[1][lst];
if(lst&&calc(lst,i)<k)return -1;
if(nxt&&k<calc(i,nxt))return 1;
ans=y[i]-k*x[i];return 0;
}
il dd query(dd k){
RG ll l=1,r=sz[rt],mid,ret;RG dd ans;
while(l<=r){
mid=(l+r)>>1;
ret=check(mid,k,ans);
if(ret==0)return ans;
else if(ret==1)l=mid+1;
else if(ret==-1)r=mid-1;
}
}
int main()
{
n=read();S=read();
for(RG int i=1;i<=n;i++)
scanf("%lf%lf%lf",&a[i],&b[i],&r[i]);
f[1]=1;insert((f[1]*r[1])/(a[1]*r[1]+b[1]),f[1]/(a[1]*r[1]+b[1]));
for(RG int i=2;i<=n;i++){
f[i]=max(f[i-1],query(-1.0*(a[i]*1.0/b[i]))*b[i]);
insert((f[i]*r[i])/(a[i]*r[i]+b[i]),f[i]/(a[i]*r[i]+b[i]));
}
printf("%.3lf
",S*1.0*f[n]);
return 0;
}
这里是(CDQ)分治的代码
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define Cpy(x,y) memcpy(x,y,sizeof(x))
#define Set(x,y) memset(x,y,sizeof(x))
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-7;
const int mod=1e9+7;
const int N=100010;
const int M=1000010;
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
srand(time(NULL)+rand());
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
}
int n,q[N],tmp[N];
dd s,a[N],b[N],r[N],f[N],x[N],y[N],k[N];
dd cx[N],cy[N];int top;
il dd getk(dd ax,dd ay,dd bx,dd by){
if(fabs(ax-bx)<eps)return ay<by?INF:-INF;return (ay-by)/(ax-bx);
}
il void insert(dd ix,dd iy){
while(top>1&&getk(cx[top-1],cy[top-1],cx[top],cy[top])<getk(cx[top],cy[top],ix,iy))top--;
top++;cx[top]=ix;cy[top]=iy;
}
il dd query(dd k){
RG int l=1,r=top,mid;
while(l<=r){
mid=(l+r)>>1;
if(mid!=1&&getk(cx[mid-1],cy[mid-1],cx[mid],cy[mid])<k)
{r=mid-1;continue;}
else if(mid!=top&&k<getk(cx[mid],cy[mid],cx[mid+1],cy[mid+1]))
{l=mid+1;continue;}
return cy[mid]-k*cx[mid];
}
}
void cdq(int L,int R){
if(L==R){
f[q[L]]=max(f[q[L]],f[q[L]-1]);
x[q[L]]=(f[q[L]]*r[q[L]])/(r[q[L]]*a[q[L]]+b[q[L]]);
y[q[L]]=f[q[L]]/(r[q[L]]*a[q[L]]+b[q[L]]);return;
}
RG int M=(L+R)>>1;cdq(L,M);top=0;
for(RG int i=L;i<=M;i++)f[i]=max(f[i],f[i-1]);
for(RG int i=L;i<=M;i++)insert(x[q[i]],y[q[i]]);
for(RG int i=M+1;i<=R;i++){
k[q[i]]=-a[q[i]]/b[q[i]];
f[q[i]]=max(f[q[i]],query(k[q[i]])*b[q[i]]);
}
cdq(M+1,R);
for(RG int i=M+1;i<=R;i++){
x[q[i]]=(f[q[i]]*r[q[i]])/(r[q[i]]*a[q[i]]+b[q[i]]);
y[q[i]]=f[q[i]]/(r[q[i]]*a[q[i]]+b[q[i]]);
}
for(RG int i=L,p1=L,p2=M+1;i<=R;i++)
if(p2>R||(p1<=M&&x[q[p1]]<x[q[p2]]))tmp[i]=q[p1++];
else tmp[i]=q[p2++];
for(RG int i=L;i<=R;i++)q[i]=tmp[i];
}
int main()
{
n=read();scanf("%lf",&s);
for(RG int i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i],&b[i],&r[i]),q[i]=i;
f[1]=1;x[1]=(f[1]*r[1])/(r[1]*a[1]+b[1]);y[1]=f[1]/(r[1]*a[1]+b[1]);
cdq(1,n);printf("%.3lf
",s*f[n]);return 0;
}