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

A

裸题，不写了

B$~~$hdu 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

D$~~$poj 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

F$~~$hdu 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

先从小到大排序

易知分在一组的都是连续一段

于是得到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

I$~~$poj 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

设$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

L

重复题目

J$~~$uva 12594