[kuangbin带你飞]专题二十 斜率DP

A 裸题，不写了 B$~~$[hdu 2829](http://acm.hdu.edu.cn/showproblem.php?pid=2829) 设$dp[i][j]$为前$i$个点分$j$段的最小值 设$val[i][j]$为$[i,j]$的点为一段时的值，$val[i]$表示$val[1][i]$ $sum[i]$为前缀和 $$val[i][j]=val[j]-val[i-1]+sum[i-1] \cdot (sum[j]-sum[j-1])$$ dp方程： $$dp[i][j]=min(dp[k][j-1]+val[k+1][i])\qquad (k<i)$$ $$\Rightarrow dp[i][j]=dp[k][j-1]+val[i]-val[k]-sum[k] \cdot (sum[i]-sum[k])$$ $$\Rightarrow sum[i] \cdot sum[k]+dp[i][j]-val[i]=dp[k][j-1]-val[k]+sum[k]^2$$ $x=sum[k]$，$y=dp[k][j-1]-val[k]+sum[k]^2$，斜率$sum[i]$单调递增，求截距$dp[i][j]-val[i]$最小值 根据$j$分别维护凸包即可 C$~~$[hdu 4528](http://acm.hdu.edu.cn/showproblem.php?pid=4528) D$~~$[poj 1260](http://poj.org/problem?id=1260) 设$dp[i]$为满足前$i$种珍珠需求最小费用 设$sum[i]$为所需珍珠数量的前缀和 dp方程： $$dp[i]=min(dp[j]+(sum[i]-sum[j]+10) \cdot p[i])\qquad (j<i)$$ $$\Rightarrow p[i] \cdot sum[j]+dp[i]-(sum[i]+10) \cdot p[i]=dp[j]$$ $x=sum[j]$，$y=dp[j]$，斜率$p[i]$单调递增，求截距$dp[i]-(sum[i]+10) \cdot p[i]$最小值 E$~~$[hdu 2993](http://acm.hdu.edu.cn/showproblem.php?pid=2993) F$~~$[hdu 3669](http://acm.hdu.edu.cn/showproblem.php?pid=3669) 以$w$为第一关键字，$h$为第二关键字降序排列 设$i<j$，则一定有$w[j]<=w[i]$ 若$h[j]<=h[i]$则一定能过，直接去掉 则剩下的序列满足$w$单调递减，$h$单调递增 对于一个后面的人$i$，要么重新开一个洞，要么将之前的一个洞加高到$h[i]$ 如果是加高，一定加高最后一个洞，证明如下： $\qquad$设最后一个洞为$w[i] \cdot h[i]$ $\qquad$那么对于任意$j<i$，都有$w[j]>w[i]$且$h[j]<h[i]$ $\qquad$则加高到$h[k]$时必有费用$w[i] \cdot (h[k]-h[i])<w[j] \cdot (h[k]-h[j])$，即$i$更优 也就是说，序列中的连续一段必定是开同一个洞的 这就将原问题转化为分组问题：将一个序列分为最多$K$组，$[i,j]$分为一组的代价为$w[i] \cdot h[j]$，求最小代价 设$dp[i][j]$为前$i$个人分$j$组的最小代价，dp方程： $$dp[i][j]=min(dp[k][j-1]+w[k+1] \cdot h[i]) \qquad (k<i)$$ $$\Rightarrow h[i] \cdot w[k+1]-dp[i][j]=dp[k][j-1]$$ 斜率优化即可 G$~~$[hdu 3045](http://acm.hdu.edu.cn/showproblem.php?pid=3045) 先从小到大排序 易知分在一组的都是连续一段 于是得到dp方程： $$dp[i]=min(dp[j-1]+(sum[i]-sum[j-1])-a[j] \cdot (i-j+1)) \qquad (T \leq i \leq n,j \leq i-T)$$ 斜率优化即可 H$~~$[hdu 3516](http://acm.hdu.edu.cn/showproblem.php?pid=3516) I$~~$[poj 1160](http://poj.org/problem?id=1160) 设$dis[i][j]$为$[V_i,V_j]$上建一个邮局的最小距离和 画图容易知道，这个邮局应该建在$V_{(i+j)/2}$的位置最优（其中$i+j$为奇数时建在$V_{(i+j)/2}$和$V_{(i+j)/2+1}$效果相同） 易知$dis[i][i]=0$ 从$dis[i][j-1]$推$dis[i][j]$时，可视为将原邮局移动到新的位置，并加上$V_j$到新邮局的距离 可以推出移动邮局对原来各村庄影响的和为0（因为比较简单所以不作证明），因此有 $$dis[i][j]=dis[i][j-1]+x[j]-x[(i+j)/2]$$ 可以$O(n^2)$预处理出$dis$ 设$dp[i][j]$为前$i$个村庄设置$j$个邮局的最小距离和，dp方程： $$dp[i][j]=min(dp[k][j-1]+dis[k+1][i]) \qquad (k<i)$$ 边界条件$dp[i][1]=dis[1][i]$ 时间复杂度$O(V^2P)$，对于本题不优化也可以过 J$~~$[poj 1180](http://poj.org/problem?id=1180) 设$dp[i][j]$为前$i$个任务分$j$组的最小代价，dp方程： $$dp[i][j]=min(dp[k][j-1]+(t+sumT[i]-sumT[k]) \cdot (sumF[i]-sumF[k])) \qquad (k<i)$$ 其中$t=s \cdot (j-1)+sumT[k]$ 斜率优化后时空复杂度都是$O(n^2)$，但本题$n=10000$，显然过不了 观察到之前用到$j$这一维是因为前面的分组数有后效性 于是反过来，设$dp[i]$为$[i,n]$的任务的最小代价，得到dp方程： $$dp[i]=min(dp[j]+(s+sumT[j-1]-sumT[i-1]) \cdot (sumF[n]-sumF[i-1])) \qquad (i<j)$$ 斜率优化后时空复杂度$O(n)$，符合要求 K$~~$[poj 2841](http://poj.org/problem?id=2841) L 重复题目 J$~~$uva 12594