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