首页 > 其他 > 详细

[NOI2016]国王饮水记

时间:2019-07-07 18:08:43      阅读:125      评论:0      收藏:0      [点我收藏+]

 [NOI2016]国王饮水记 

.....无话可说

小于h1的直接扔掉

其他的从小到大排序

k>n的时候,手玩可以发现,每次选择2个合并最优

k<n?一段合并答案更优

DP,f[i][j]前i个,合并了j次最大值

可以推出斜率优化的式子,(这个有所不同!这玩意是分式,最优化斜率,交叉项才是最优化截距!)

也具有决策单调性,下凸壳队列维护

 

n<=700的时候,用高精度

n>700的时候直接long double拿40%

这样可以有91pts

 

然后开始 

 

法一:直接f[i][j]用long double存答案,记录转移的路径,最后高精度还原.....不知道为什么f精度可以支持比大小的时候不错.

法二:可以证明,分段>=2只有不超过14个,一定是前14个

 

无话可说....

 

斜率优化的分式形式不太常见

[NOI2016]国王饮水记

原文:https://www.cnblogs.com/Miracevin/p/11146801.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!