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

2018-01-27 13:34:33

A

B$~~$hdu 2829

$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]$最小值

C$~~$hdu 4528

D$~~$poj 1260

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

$\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$更优

$$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[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]=dis[i][j-1]+x[j]-x[(i+j)/2]$$

$$dp[i][j]=min(dp[k][j-1]+dis[k+1][i]) \qquad (k<i)$$

J$~~$poj 1180

$$dp[i][j]=min(dp[k][j-1]+(t+sumT[i]-sumT[k]) \cdot (sumF[i]-sumF[k])) \qquad (k<i)$$

$$dp[i]=min(dp[j]+(s+sumT[j-1]-sumT[i-1]) \cdot (sumF[n]-sumF[i-1])) \qquad (i<j)$$

K$~~$poj 2841

L

J$~~$uva 12594

• star
首页