lkMiles

退役oier

uestc 879 摩天轮

一道裸的斜率优化。

我记得gnaw来讲dp的时候例题就是这个,然而当时似懂非懂的现在才理清楚。

关于斜率优化,不同的人有不同的写法,但我最后还是选择了用线性规划的思路。当遇到f(n)=min(f(k)+a[n]*b[k]+g(k))这种形式的时候我们可以把它抽象成平面上的点(b[k],g(k)+f(k)),这些都是与n无关的部分,那我们拿到一个n,就要去找minC=a[n]*X+Y,这里的XY对应的是上面的那个坐标,化简一下得到Y=-a[n]*X+C,变成一条直线从负无穷的地方网上移动切到第一个点就是要找的那个点,而且一定满足这样的性质,这个点和它左右两个点的斜率一定把这条线的斜率夹在中间。根据高中数学知识,那些切到的点只会在凸包上,所以整个过程就是:

1.拿到当前斜率,找到合适点,更新当前dp值

2.用dp值继续构建一个点,加入凸包中(会有必要的删点)。

如果对于不断变化的n我们拿到的斜率是单调的,那么就可以直接用单调队列维护,因为以前用不了的现在也用不了,但是如果拿到的斜率不是单调的,可能就需要在凸包上进行二分了,虽然现在还没写过ovo

坑点:有可能没有斜率,可能需要特判然后赋极大值

最后吐槽一下坑大,maya我开个longlong判我TLEsmg!改成int为什么就能过- -。

题面:http://acm.uestc.edu.cn/#/problem/show/879

code:http://paste.ubuntu.net/15331736/

昨天的考题终于调出来啦!第一次写凸包上的二分呢然后分成两部分一直拍拍拍了好久才de出bug,看了那些bug真的觉得自己好蠢好蠢好蠢,就连忘记打括号,斜率算错这种都要犯QAQ

code:http://paste.ubuntu.net/15332564/

题号是oj7的1466

评论
热度(1)
©lkMiles
Powered by LOFTER