1492: [NOI2007]货币兑换Cash DP+斜率优化+splay维护凸包/CDQ分治

发布时间:2021-10-27 07:06:53

似乎两个月之前我写过一次这题写挂了?
《多年的心头大恨终于解决了系列》
我们可以发现,存在最优解满足每次将全部的钱买了券或每次将全部的券卖成钱,因为有利益我们要尽可能的去获得,有亏损就一点也不要碰。
我们用

fi
表示到

i
天时的最大收益,令xi,yi分别表示第

i
天购买A券和

B
券的数量。则如果将第i天的收益全部买成券,那么满足





fi=Ai?xi+Bi?yi



因为有



xiyi=ratei
,我们代入上式,可以得到:






yi=fiAi?ratei+Bi,xi=yi?ratei=fi?rateiAi?ratei+Bi



状态转移方程显然:






fi=max{Ai?xj+Bi?yj}



变形得:






yj=?AiBi?xj+fiBi



可以发现这是一个直线方程的形式,其中斜率为



?AiBi
,截距为



fiBi
,我们要使



fi
最大化,也就是使截距最大化。

我们知道决策点一定在一个上凸包上,而对于一些点的横坐标



xi
递增的题目,我们可以用单调队列来维护一个凸包,如果每个



i
对应的斜率也单调,我们可以根据决策单调性来线性维护,如果斜率不单调,我们可以在单调队列上二分。而这道题目点的坐标和斜率都不单调,我们需要动态维护一个凸包,并且支持加点,删点,查询前后点等操作,因此可以用splay来维护。

Time:936 ms Code_Length:2550 B,可以发现是比较优秀的。



然后还有一种比较神奇的方法,叫做cdq分治。
主要思想就是离线处理,化无序为有序
我们可以发现,每个点对应的斜率为

?AiBi
,与其他值无关,也就是说一个点

xi
引入后,对后面的点产生的影响是确定的。
我们考虑分治。
定义这样一个过程

solve(l,r)
,假设调用后可以求得

fi(l<=i<=r)
。那么对于区间

[l,mid]
的询问,可以直接递归调用

solve(l,mid)
得到,对于区间

[mid+1,r]
的询问

K
,会受到[l,mid]以及

[mid+1,K]
的影响,后半部分可以递归解决。我们考虑前半部分。
我们整体考虑

[l,mid]


[mid+1,r]
的影响,第一个区间的每一个点都可能成为第二个区间某一个询问的决策点,那么我们不妨维护第一个区间对应点集的凸包,然后把第二个区间的询问按斜率排序,这样

O(n)
的时间内就可以完成所有的查询。
具体的说,我们首先对所有询问按照斜率排序,然后在分治的时候,按照位置在

mid
的左右分类,这样形成了两个按照斜率排好序的区间然后递归。然后合并的时候,就对点集进行归并排序。整个过程的复杂度是

O(nlogn)
的。
可见这个算法是非常优秀的,更多关于CDQ分治的东西还需要我去探究,这只是做的第一道入门的题目,理解的还不是很深啊。
Time:1204 ms Code_Length:1832 B,代码量减小了不少。其实我觉得还是splay写起来顺手


splay


#include
#include
#include
#define eps 1e-9
#define inf 1e9
#define N 100005
using namespace std;
int fa[N],tree[N][2];
double f[N],x[N],y[N],a[N],b[N],lk[N],rk[N],rate[N];
int n,m,root;
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=tree[y][1]==x,r=l^1;
if (y==k) k=x; else tree[z][tree[z][1]==y]=x;
fa[x]=z; fa[y]=x; fa[tree[x][r]]=y;
tree[y][l]=tree[x][r]; tree[x][r]=y;
}
inline void splay(int x,int &k)
{
while (x!=k)
{
int y=fa[x],z=fa[y];
if (y!=k)
{
if (tree[y][0]==x^tree[z][0]==y) rotate(x,k); else rotate(y,k);
}
rotate(x,k);
}
}
inline void insert(int &k,int f,int id)
{
if (!k)
{
k=id;
fa[k]=f;
splay(k,root);
return;
}
if (x[id]<=x[k]+eps) insert(tree[k][0],k,id);
else insert(tree[k][1],k,id);
}
inline double getk(int i,int j)
{
if (fabs(x[i]-x[j]) else return (y[j]-y[i])/(x[j]-x[i]);
}
inline int prev(int k)
{
int t=tree[k][0],tmp=t;
while (t)
{
if (getk(t,k)<=lk[t]+eps) tmp=t,t=tree[t][1];
else t=tree[t][0];
}
return tmp;
}
inline int succ(int k)
{
int t=tree[k][1],tmp=t;
while (t)
{
if (getk(t,k)+eps>=rk[t]) tmp=t,t=tree[t][0];
else t=tree[t][1];
}
return tmp;
}
inline void update(int k)
{
splay(k,root);
if (tree[k][0])
{
int left=prev(root);
splay(left,tree[k][0]); tree[left][1]=0;
lk[k]=rk[left]=getk(left,k);
}
else lk[k]=inf;
if (tree[k][1])
{
int right=succ(root);
splay(right,tree[k][1]); tree[right][0]=0;
rk[k]=lk[right]=getk(right,k);
}
else rk[k]=-inf;
if (lk[k]<=rk[k]+eps)
{
root=tree[k][0]; tree[root][1]=tree[k][1];
fa[tree[k][1]]=root; fa[root]=0;
rk[root]=lk[tree[k][1]]=getk(root,tree[k][1]);
}
}
inline int find(int k,double slop)
{
if (!k) return 0;
if (lk[k]+eps>=slop&&slop+eps>=rk[k]) return k;
else if (slop+eps>lk[k]) return find(tree[k][0],slop);
else return find(tree[k][1],slop);
}
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]);
for (int i=1;i<=n;i++)
{
int j=find(root,-a[i]/b[i]);
f[i]=max(f[i-1],x[j]*a[i]+y[j]*b[i]);
y[i]=f[i]/(a[i]*rate[i]+b[i]);
x[i]=y[i]*rate[i];
insert(root,0,i);
update(i);
}
printf("%.3lf
",f[n]);
return 0;
}

cdq


#include
#include
#include
#include
#define inf 1e9
#define eps 1e-9
#define N 100005
using namespace std;
struct query {int id; double a,b,k,rate;} q[N],nq[N];
struct point {double x,y;} p[N],np[N];
double f[N];
int stack[N];
int n;
inline bool operator<(query a,query b)
{
return a.k}
inline bool operator<(point a,point b)
{
return fabs(a.x-b.x)<=eps?a.y}
inline double slop(int i,int j)
{
if (!i) return -inf;
if (!j) return inf;
if (fabs(p[i].x-p[j].x)<=eps) return -inf;
return (p[i].y-p[j].y)/(p[i].x-p[j].x);
}
void solve(int l,int r)
{
if (l==r)
{
f[l]=max(f[l],f[l-1]);
p[l].y=f[l]/(q[l].a*q[l].rate+q[l].b);
p[l].x=p[l].y*q[l].rate;
return;
}
int mid=l+r>>1,p1=l,p2=mid+1;
for (int i=l;i<=r;i++)
if (q[i].id<=mid) nq[p1++]=q[i];
else nq[p2++]=q[i];
for (int i=l;i<=r;i++) q[i]=nq[i];
solve(l,mid);
int top=0;
for (int i=l;i<=mid;i++)
{
while (top>=2&&slop(i,stack[top])+eps>slop(stack[top],stack[top-1])) top--;
stack[++top]=i;
}
int j=1;
for (int i=r;i>=mid+1;i--)
{
while(j f[q[i].id]=max(f[q[i].id],q[i].a*p[stack[j]].x+q[i].b*p[stack[j]].y);
}
solve(mid+1,r);
p1=l; p2=mid+1;
for (int i=l;i<=r;i++)
if ((p[p1]r)&&p1<=mid) np[i]=p[p1++]; else np[i]=p[p2++];
for (int i=l;i<=r;i++) p[i]=np[i];
}
int main()
{
scanf("%d%lf",&n,&f[0]);
for (int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].rate);
q[i].k=-q[i].a/q[i].b;
q[i].id=i;
}
sort(q+1,q+n+1);
solve(1,n);
printf("%.3lf
",f[n]);
return 0;
}

相关文档

  • 水景拍摄方法技巧
  • Unity Shader之模板测试
  • 类风湿关节炎的早期诊断及治疗_类风湿关节炎怎么治疗
  • 蓝桥杯2018年A组三体攻击题解
  • 自主招生和统招有什么区别自主招生的国家承认学历吗
  • 跳棋游戏规则及好处
  • BigDecimal的数值是否相等的判断(equals与compareTo)
  • Spring事务自行整理验证
  • 贝佐斯宣布三季度卸任亚马逊CEO 接任者是云计算业务CEO
  • 高效的职场工作法则有哪些
  • 多肉植物观察日记三则
  • 养金鱼的风水有哪些
  • 四年级下学年学生评语
  • 纸质文件怎么扫描成电子版
  • 华为荣耀10收不到验证码
  • 淘宝双11购物津贴那里领取
  • 幼儿园中班幼儿健康教案《同伴生病了》含反思
  • 抗抑郁用药禁忌有哪些
  • 对于《关于使用Delphi XE10 进行android开发的一些总结》的补充
  • 圆白菜怎么炒才好吃?干煸圆白菜的做法
  • rancher的使用感受以及与k8s的对比
  • 小学生开学第一课安全教育班会
  • 儿童眼保健小知识
  • 最新大寿对联
  • 煤矿安全责任书
  • 三年级叙事作文,:全国爱牙日 150字|三年级爱牙日手抄报
  • 优秀日记范文:开学
  • 信心的反义词
  • 办公室主任竞聘报告
  • bugsplat.dll英雄联盟修复文件
  • 猜你喜欢

    电脑版