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

· · 个人记录

A

裸题，不写了

B~~hdu 2829

设dp[i][j]为前i个点分j段的最小值

设val[i][j]为[i,j]的点为一段时的值，val[i]表示val[1][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] 也就是说，序列中的连续一段必定是开同一个洞的 这就将原问题转化为分组问题：将一个序列分为最多$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

设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