关键词：斜率优化，四边形不等式优化
1.斜率优化
斜率优化一般对f[i]=f[j]+ \(A_i B_j\) 一类的式子进行优化加快转移时间，将式子类似到 \(b = y - k x\)普遍所以最值就是寻找b的最值
例题1
本题转移方程是 \(f[i] = min_{j<i} (f[j]+(s_i - s_j - 1 + l)^2)\) 其中 \(s_i = \sum_{i=1}^i (c[i]+1)\) 直接写时间复杂度O( \(N^2\) )，明显tle，需要进行优化
假设f[i]的转移点为 \(j_0\)
所以可以得到 \(f[i] = f[j_0]+(s_i - s_{j_0} - 1 + l)^2\) 为了方便先令 \(l'=l+1\)
原式变为 \(f[i] = f[j_0]+(s_i - s_{j_0} - l')^2\)
\(f[i] = f[j_0] + s_{j_0}^2 + s_i^2 + l'^2 - 2s_i s_{j_0} - 2s_i l'+2s_{j_0} l'\)
\(f[i] = f[j_0] + s_{j_0}^2 + s_i^2 + l'^2 - 2s_i s_{j_0} - 2s_i l'+2s_{j_0} l'\)
将只有i放到左边得到
\(f[i] - (s_i^2 - 2s_i l') = f[j_0] + s_{j_0}^2 + 2s_j l' + l'^2 - 2s_i s_{j_0}\)
$f[i] - (s_i^2 - 2s_i l') = f[j_0] + ( s_{j_0} + l' )^2 - 2s_i s_{j_0} $
与一次函数对比
$ \qquad \qquad b \qquad \quad = \qquad \qquad y \qquad \quad - k \quad x $
可以发现\begin{cases}
b = f[i] - (s_i^2 - 2s_i l') \\
y_{j_0} = f[j_0] + ( s_{j_0} + l' )^2 \\
k = 2s_i \\
x_{j_0} = s_{j_0}
\end{cases}
把所有(x,y)都画到平面坐标系里面，会发现转移点应该满足b最小，k也随着i增加而变大，所以转移点一定在下面外围一些点
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+1;
long long n,l,f[N],sum[N],c[N];
int a[N],head=1,tail=1;
double js(int x,int y){return ((f[x]+(sum[x]+l+1)*(sum[x]+l+1))-(f[y]+(sum[y]+l+1)*(sum[y]+l+1)))/(sum[x]-sum[y]);
}
int main(){cin>>n>>l;for(int i=1;i<=n;i++){cin>>c[i];sum[i] = sum[i-1]+c[i]+1;}memset(f,0x3f3f3f,sizeof(f));a[1]=0;f[0]=0;sum[0]=0;for(int i=1;i<=n;i++){while(head<tail && js(a[head],a[head+1]) <= 2*sum[i])++head;f[i]=f[a[head]]+(sum[i]-sum[a[head]]-1-l)*(sum[i]-sum[a[head]]-1-l);while(head<tail && js(a[tail-1],a[tail]) >= js(a[tail],i))tail--;a[++tail]=i;}cout<<f[n]<<"\n";return 0;
}
2.四边形不等式优化
"四边形不等式优化利用的是状态转移方程中的决策单调性，也常称为决策单调性优化 DP"
对于f[i]=min(f[j]+w(i,j))的式子，并且满足下面要求即满足四边形不等式则存在决策单调性可以使用四边形不等式优化
\(任意a \le b \le c \le d时，w(a,d)+w(b,c) \ge w(a,c)+w(b,d)\)
例题1
可以写出 \(f[l][r] = min_{j < i}(f[l][k] + f[k+1][r] + w(l,l+i))\)
\(w(l,l+i)=s[l+i]-s[l-1]\) 很容易发现w(i,j)满足四边形不等式,令opt[l][r]为f[l][r]的最佳转移点，会发现opt也是不下降序列
我们发现 \(opt[l][r-1] \le opt[l][r] \le opt[l+1][r]\) 这个范围就是第三层循环的范围，可以缩减时间复杂度
#include <bits/stdc++.h>
using namespace std;
int n,a[305],f[305][305],s[305],opt[305][305];
int main(){cin>>n;memset(f,0x3f3f3f,sizeof(f));for(int i=1;i<=n;i++){cin>>a[i];f[i][i]=0;s[i]=s[i-1]+a[i];opt[i][i]=i;}for(int i=1;i<=n;i++){for(int l=1;l+i<=n;l++){int t=INT_MAX;int ti=0;for(int k=opt[l][l+i-1];k<=opt[l+1][l+i];k++){if(t > f[l][k]+f[k+1][l+i]+s[l+i]-s[l-1]){t = f[l][k]+f[k+1][l+i]+s[l+i]-s[l-1];ti = k;}}f[l][l+i]=t;opt[l][l+i]=ti;}}cout<<f[1][n];return 0;
}
例题2：简化题目，有v个村庄，装p个邮局，求村庄到邮局距离之和的最小值
我们可以写出 \(f[i][j] = min_{k<i}(f[k][j-1] + w(k+1,i))\) , \(f[i][j]表示[1,i]区间放j个邮局的答案,w(k+1,i)是将[k+1,i]目标放到同一个邮局距离之和最小值\)
证明可得w(k+1,i)满足四边形不等式，令opt[i][j]为f[i][j]的最佳转移点
可以发现\begin{cases}
opt[i+1][j] \le opt[i][j] \le opt[i-1][j] \\
opt[i][j-1] \le opt[i][j] \le opt[i][j+1]
\end{cases}
由于使用上面范围的前提是里面存过数
取 \(opt[i][j-1] \le opt[i][j] \le opt[i+1][j]\)
#include <bits/stdc++.h>
using namespace std;
const int N = 3006;
long long n,p,a[N],f[N][305],opt[N][305],w[N][N];
int main(){cin>>n>>p;for(int i=1;i<=n;i++){cin>>a[i];opt[i][i]=i;}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){w[i][j]=w[i][j-1]+a[j]-a[(i+j)>>1];}}memset(f,0x3f,sizeof(f));for(int i=1;i<=n;i++){f[i][1]=w[1][i];opt[i][1]=0;}sort(a+1,a+n+1);for(int j=2;j<=p;j++){opt[n+1][j]=n;for(int i=n;i>=1;i--){for(int k=opt[i][j-1];k<=opt[i+1][j];k++){if(f[i][j] > f[k][j-1]+w[k+1][i]){f[i][j]=f[k][j-1]+w[k+1][i];opt[i][j]=k;}}}}cout<<f[n][p]<<"\n";return 0;
}