搜索
您的当前位置:首页正文

bzoj1492(货币兑换Cash 斜率优化dp+cdq分治维护凸壳 入门题)

来源:独旅网



不可能存在第2天买 第4天买 第五天卖 第六天卖 这种情况。
不可能存在第2天买 第4天买 第五天卖 这种情况。
不可能存在第4天买 第五天卖 第六天卖 这种情况。
也就是第2天买 第三天卖 第五天买 第7天卖
多次买卖只能一段一段的 不能交叉。而且是倾巢买完/卖完!!!!!
先用所有的本金前几天赚一点钱 然后再用这些钱再买完在卖赚点钱 直到最后一天


假如第 j 天最多可以拥有的钱为 dp[j] .
则该天得到的A券为(dp[j]*r[j])/(a[j]*r[j]+b[j]) B券为dp[j]/(a[j]*r[j]+b[j]).
第 i 天想得到最多的钱的话就要决定1-(i-1) 从哪一天买券。
dp[i]=max(X[j]*a[i]+Y[j]*b[i]) 每个i依靠前面的X[j] Y[j] (也就是dp[j] 因为dp[j]决定X[j] Y[j])
就是斜率优化的模型啦。
emmm与普通的斜率优化dp入门题有点不同啊。 这里怎么有两个X[j] Y[j] 带着 i 且关于 j 的变量。两边同时➗b[i]就好了啊。
先不管那么多。。 Y[j]=(-a[i]/b[i])*X[j]+dp[i]/b[i].
要查询的斜率(-a[i]/b[i]) 横坐标X[j] 纵坐标Y[j]全都不单调。。。采用cdq分治维护凸壳 查询与增添决策放在一起处理 边添加边查询。

#include<cstdio>
#include<cmath>
#include<algorithm>
#define eps 1e-9
using namespace std;
typedef double du;
const du INF=1e9;
const int N=1e5+5;
du dp[N];int st[N];//单调栈(很简单的单调栈 不涉及左右界点) 维护斜率单调递减的栈(上凸壳的顶点)
struct node{du a,b,r,K,X,Y;int id;}q[N],tmp[N];
int cmp(node x,node y){return x.K<y.K;}
inline du getK(int i,int j){
    if(fabs(q[i].X-q[j].X)<eps) return -INF;
    return (q[i].Y-q[j].Y)/(q[i].X-q[j].X);
}
void cdq(int l,int r){//每次cdq(l,r)结束后 dp[i](l<=i<=r)都被更新了.
    if(l==r){
//        if(l!=q[l].id) puts("ooo");//加这句话也ac了 只是为了测试l一定等于q[l].id
        dp[l]=max(dp[l],dp[l-1]);//因为一次次分治 到l==r这种时 比l的id小的一定完全都被考虑过是否可以更新l了 因为每次cdq会先按id排序 id比它小的一定先比他经历cdq这个过程
        q[l].Y=dp[l]/(q[l].a*q[l].r+q[l].b),q[l].X=q[l].Y*q[l].r;//这一天最多得到的钱可以买的A券数量X B券数量Y.会对以后id比他大的有影响 假如这个决策点
        return;
    }
    int mid=(l+r)>>1,t1=l,t2=mid+1;
    for(int i=l;i<=r;++i){//q[i].id一定在[l,r]之间
        if(q[i].id<=mid) tmp[t1++]=q[i];//放入左区间的id一定位于[l,mid]之间
        else tmp[t2++]=q[i];//放入右区间的id一定位于[mid+1,r]之间
    }//不改变左区间的斜率递增 右区间的斜率递增的性质   &&顺便保证了左区间的所有id都小于右区间 但左右子区间内部无序(无所谓)
    for(int i=l;i<=r;++i) q[i]=tmp[i];
    cdq(l,mid);//cdq(l,mid)会将[l,mid]的横坐标(建立在坐标系里面的)从小到大排序
    int top=0;//每次维护左区间凸壳 查询右区间 弄一个新的单调栈与分治毫无关系
    for(int i=l;i<=mid;++i){//维护上凸壳(斜率递减)  此时左区间斜率无序但斜率优化坐标系里的X横坐标有序(它斜率无序无任何影响 要斜率有序也没什么用)
        while(top>=2&&getK(st[top-1],st[top])<=getK(st[top],i)) --top;
        st[++top]=i;
    }
    for(int i=mid+1;i<=r;++i){//由于右区间斜率递增的性质 不符合查询第一个的决策点一定不符合后边的 所以下一行可以--top. 
        while(top>=2&&getK(st[top-1],st[top])<q[i].K) --top;//找到第一个斜率>=q[i].k的 更新q[i].id的答案(这里要注意!!!不是更新dp[i] 而是更新dp[q[i].id])
        int j=st[top];
        dp[q[i].id]=max(dp[q[i].id],q[j].X*q[i].a+q[j].Y*q[i].b);
    }
    cdq(mid+1,r);
    int i=l,j=mid+1,k=l;//下面由于左区间[l,mid]的X有序 右区间[mid+1,r]X有序 可以归并排序 使得[l,r]整个序列X有序 
    while(i<=mid&&j<=r){
        if(q[i].X<q[j].X) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(int i=l;i<=r;++i) q[i]=tmp[i];
}
int main(){
    int n;scanf("%d%lf",&n,&dp[0]);
    for(int i=1;i<=n;++i){
        scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].r);
        q[i].K=-q[i].a/q[i].b,q[i].id=i;
    }
    sort(q+1,q+n+1,cmp);//将查询的斜率从小到大排序 可以保证每次cdq时左右区间斜率递增 每次将整个区间按id划分(并不是按id排序) id<=mid去左边 否则去右边 可以不改变左右子区间斜率递增的性质 也可以保证左边的id一定小于右边的.
    cdq(1,n);//cdq左边后 左区间按X排序(才能维护凸壳) 右区间斜率有序(可以尺取查找 不用二分了)
    printf("%.3f\n",dp[n]);
}

因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top