首页 > 小睿睿的疑惑
开通博客写题解
头像 __故人__
发表于 2020-09-17 20:59:17
分析 令 为以 结尾的最小代价。 ，后面的可以前缀和优化一下。 。令 为 的决策点，那么可以化简为 。那么这个就是个一次函数。其中 ，所以为了让 最小，那么我们显然要让 最小。那么现在就是要求 的最小值，放在坐标轴上，就是求直线 与所有一次函数的最小值，这个可以李超线段树来求 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-18 11:40:33
分析 看完题，首先这绝对是一个DP题我们设 Height[]表示高度 Cost[]表示花费 DP[]表示以当前点为截至点的花费最小值 Pre[]表示花费的前缀和 算法一 那么DP方程： 那么我们就得到了一个的转移方程式 算法二 我们发现，对于每次的修改，需要的只是最后一次从转移到的最小值那么我们 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”