加载中…
正文 字体大小:

斜率优化 二

(2012-02-01 19:11:35)
标签:

杂谈

  前几天主要做了几道斜率优化的题目,在这里总结一下。
  首先看看2004年国家集训队周源的论文中的《最大平均值问题》:给出正数a[1..n]及f,求连续至少f个数的最大平均值。
  设部分和数组为S,则容易得到方程 (S[i]-S[j-1])/(i-j+1),这可以看做(i,S[i])和(j,S[j])的斜率,那么问题转化为求n个点中水平距离至少为f的最大斜率。
  在前一篇总结中就举了几道运用斜率优化解决的题目,但并没有深入理解斜率优化的真正含义。对于这题求最优的j相当于求i与各点连线方程 y=kx+b 中最小的b,容易知道最优的j必定在点围成的下凸折线上,且j恰好是i与折线的切点。这个下凸折线可以用单调队列维护,但队头与队尾的删除有着完全不同的意义:队尾的删除是因为新的(i,S[i])的插入,也许会影响折线的下凸性(像求凸包时的调整);而队头则是因为随着i的增长(图中Q点上移),点Q与折线的切点P也会随着改变(单调逆时针旋转,上一总结中设决策j,k并进行比较),但当缺乏单调性时则不能这样做,转而用平衡树、二分来维护并查找。之前因为对斜率优化没有理解透彻而犯了错误。
斜率优化 <wbr>二


pku 3709
  题目大意,给出一个n个数的非降序列a[1..n]和k,现把n个数分成连续的若干组,每组的数都变成同组中最小的数,问众多分组方案中的最小改动花费是多少。
  很容易得到dp方程:f(i)=min( f(j) + S[i]-S[j] - a[j+1]*(i-j) )
  我们把方程拆开并整理得到:
          f(j) = i * a[j+1] + f(i)-S[i]+S[j]-a[j+1]*j
  类比:   y   = k *    x   +          b
  这就是过点i与枚举的j的直线方程,观察知道 b 中除 f(i) 外均为常量,故求最小的f(i)即求最小的b,而通过数学知识知道这个最小的 b 在j为切点的切线方程时取到。这与上一题相似,是与比较决策量j,k优劣不同的另一种对下凸折线的解释。

pku 1180
  题目大意,给出n个任务的独立完成时间T[i]和独立完成花费F[i],只有一台机器且机器每次需启动时间S,现把n个任务分成连续的若干组,每组任务的花费为完成时刻与完成花费总和的乘积,问最小花费。
  题目有点难理解,但理解后不难写出方程:设f(i,p)为前i个任务分成p组的最小花费,则有
    f(i,p) = min( f(j,p-1) + [ sumT(1,i) + p * S ] * sumF(j+1,i) )
  即使用上斜率优化也是O(n^2),还是超时,怎么办呢?
  这显然就是状态的问题了,有10^8个状态,即使转移时间O(1)也弄不起来啊,所以要从状态入手。我纠结了许久,最后总算发现一些东西:之所以要多一位状态p,是因为日后转移时要用到p,比较 f(j,p) 与 f(j,p-1) 对日后影响无非就是多了一个 S * sumF(j+1,n),要是把这个花费提前计算不就可以把 f(j,p) 与 f(j,p-1) 统一起来了吗?于是我们得到新的方程:
    f(i) = f(j) + sumT(1,i) * sumF(j+1,i) + S * sumF(i+1,n)
  于是这题就解决了,网上还有另外的做法好像是从n做到1,大概也是把p消掉的思路(不消不行啊  空间撑不住)
  通过这题,我还认识到另外一点:斜率优化有时候很强大,可以把时间复杂度降下一维,但它不是万能的,要得到优秀的算法,还需要多方面诸如状态数、转移时间什么的结合起来才可以

icpc2011 F works
  题目大意,有一公司开始有C元,经营D天,这D天内通过买进卖出机器并工作获取利润,给出n台机器的信息:机器i仅在di天出售,买入价格pi,卖出价格ri,每天工作获利gi。公司一天内只能拥有一台机器,且买买机器的交易日机器不投入工作,问D天后最大获利。
  容易知道公司将在同一天买入卖出机器,按机器出售时间升序排序,以机器出售时间为阶段,设f(i)为买入机器i当天剩下的钱,则有:
    f(i) = max( f(j) + (di-dj-1) * gj + rj - pi )
  若f(i)<0则意味机器i不可能被购买,特殊处理下面不作讨论。
  用同样的方法设决策量j,k(j<k),若k比j优则有:
    F(k) - F(j) > -di * ( gk - gj )  
  其中 F(k) = f(k) - ( dk + 1 ) * gk + rk  
  与普通的斜率优化不同,这里的g没有单调
  一种解决方法就是用平衡树,动态维护这个凸壳。

  另一种方法是,虽然我们不知道(gk-gj)的正负,不可以随便乘除,但我们换一个角度想,①等价于:
    F(k) + di * gk > F(j) + di * gk  
  ③看似没什么特别,但意义大有不同,不等式左右在几何上相当于一条直线,而不等式意味着两直线“互相追赶”,如图:
斜率优化 <wbr>二斜率优化 <wbr>二

  第(2)幅图表明 di<d 时点j比k优,否则k比j优,于是我们只需维护一个这样的下凸折线:
斜率优化 <wbr>二
    至于图中红线由于“永无出头之日”而可以完全忽略(形象一点就是本金不够别人多,挣钱不够别人快),对于剩下的直线 y=F(p)+gp*di,我们把其按F降序排序并看成点(gp,F(p)),于是F递增,g递减。感觉像是要动态维护半平面交,但有一种来自hsl同学的线段树维护的做法,具体可以访问以下地址:

  http://blog.sina.com.cn/s/blog_8c2b659401011lgc.html

    这是一种很不错的做法,令我再一次认识到线段树的强大之处,提供了一种新的思路:虽然我们看似要维护一个半平面交,直线的交点也就是折线的拐弯地方看似很重要,但实际上我们并不在乎这些点,我们真正需要的只是横坐标为整数时的最优决策。

0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有