高度由习惯堆积

分类 算法:斜率优化dp 下的文章

BZOJ2726 SDOI2012 任务安排

题目机器上有N个需要处理的任务,它们构成了一个序列。这些任务被标号为1到N,因此序列的排列为1,2,3...N。这N个任务被分成若干批,每批包含相邻的若干任务。从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti。在每批任务开始前,机器需要启动时间S,而完成这批任务所需的时间是各个任务需要时间的总和。注意,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系...

POI2006 ZAB-Frogs

题目一群青蛙正在摧毁Byteotia所有的庄稼. 一个叫Byteasar的农夫决定使用一种放在田里的奇特的"scarefrogs"来吓跑他们, 所有的青蛙在跳跃过程中都尽量使自己离他们越远越好, 即是让自己离最近的scarefrog越远越好. Byteasar的田是块矩形的土地. 青蛙们跳跃的方向平行于坐标轴并且每次跳跃的距离为1. 一条跳跃路线的scarefrogs-距离为路径上所有点距离...

NOI2014 购票

各位dalao的解法都好神啊。。。这里给一种点分治的解法。题目链接思路首先斜率部分。转移方程:$ans[x]=min(-dis[u]*p[x]+ans[u])+dis[x]*p[x]+q[x]$发现结果只与$min()$框内的部分有关,观察这个形式,发现是个一次函数,也就是说可以斜率优化。dalao们对于推斜率式子这部分表示很不屑,但是我太菜了,所以还是写一下吧。令$p=p[x]$,当$u$...
February 17, 2019

BZOJ1597 土地并购

题目Kano准备扩大他的农场,眼下必须购买N块长方形土地。如果Kano买一块土地,价格就是土地的面积。他也可以选择并购多块土地,并购的价格为这些土地中最大的长乘以最大的宽,比如Kano购买3x5和5x3的土地,只需要支付5x5=25元,比分开买合算。请你帮他计算购买所有土地的最小费用。思路设矩形的长宽分别为$h$,$w$.首先明确一个贪心:当一个矩形的长和宽都小于另一个矩形的时候,那么这个矩...