Meaning
若有函数 \(a[i,j]\) ，令 \(i<i+1<=j<+1'\) ，若有：
\[ a[i][j]+a[i+1][j+1]\le a[i][j+1]+a[i+1][j] \] 则我们称函数 \(a\) 满足四边形不等式。General
若我们在 \(DP\) 过程中会用到类似如下形式的方程：
\[ dp[i][j]=Min(dp[k][j]\ or\ dp[i][k]+dp[k+1][j])+w[i][j] \] 那么，只要代价函数 \(w\) 满足四边形不等式，那么函数 \(dp\) 一般也会满足四边形不等式。同时，假设 \(s[i][j]\) 为当 \(dp[i][j]\) 取得最优值的决策点，即：\(dp[i][j]=dp[s[i][j]]+w[i][j]\) ，一般 \(s\) 函数也会满足四边形不等式，这样，通过移项我们会得到：\[ s[i+1][j]\le s[i][j]\le s[i][j-1] \] 或是：\[ s[i][j-1]\le s[i][j]\le s[i+1][j] \] 那么我们选取决策点的转移范围就变小了，对于枚举决策点的复杂度为 \(O(n)\) 的转移方程，它的枚举复杂度经过均摊，这个 \(O(n)\) 将会变成常数级别，常常能使 \(n^3\) 的 \(DP\) 降为 \(n^2\)。Example 1--石子合并
Problem
给你环形排列的 \(n\) 堆石子 \((n\le 100)\) ，第 \(i\) 堆石子数量为 \(a_i\) ，每次选择相邻的两堆合并，每次合并的代价将会是两堆石子的数量之和，问将所有石子合并成一堆的最大与最小代价分别是多少。
First Mentality
不难想到，首先断环为链，使之变成一条两倍长度的链，然后做 \(n^3\) 的区间的 \(dp\) 。
设 \(w[i][j]\) 为区间 \([i-j]\) 的石子数量之和， \(fmin[i][j],fmax[i][j]\) 为合并区间 \([i-j]\) 的最小、最大代价，初始状态为 \(fmin[i][i]=fmax[i][i]=0\) ：
枚举 合并的区间长度 len (2~n) 枚举 合并区间的左端点 i (1~n) 枚举 区间合并点 j (i~i+len-2) { fmin[i][i+len-1]=Min(fmin[i][j]+fmin[j+1][i+len-1])+w[i][j] fmax[i][i+len-1]=Max(fmax[i][j]+fmax[j+1][i+len-1])+w[i][j] } 这样我们就得到了一个 \(n^3\) 的 \(dp\) ，虽然对于题目来说确实够用了，但是如果 \(n\le 1000\) 呢？这时候我们应该考虑如何优化。
最小代价四边形不等式优化
可以观察到 \(fmin\) 的转移式满足使用四边形不等式的基本特征，同时，\(w\) 函数也满足四边形不等式。那么，我们可以考虑使用四边形不等式了：
利用决策点的单调性 \(s[i][j-1]\le s[i][j]\le s[i+1][j]\) 来优化第三层循环即可，初始状态为：\(s[i][i]=i\) 。
枚举决策点转移时同时更新 \(s[i][j]\) 来决策就好。
最大代价决策点优化
首先有这样一个结论：\(f[i][j]\) 的最优决策点必定在 \(i\) 与 \(j-1\) 两者之间。
考虑如何证明，反证法奉上：
设 \(w[i][p]\) 与 \(w[p+1][j]\) 的差值函数为 \(S=w[i][p]-w[p+1][j]\) ，可以观察到此函数单峰。
- 对于 \(S>=0\) 的情况：
若最优决策点为 \(i< p< j-1\) ，我们设 \(s[p+1][j]=k\) ，那么相应转移方程为：
\[ f[i][j]=f[i][p]+f[p+1][k]+f[k+1][j]+w[p+1][j]+w[i][j] \] 对应的，我们的合并方案为：\[ (a[i],a[i+1],...,a[p])U((a[p+1],a[p+2],...,a[k])U(a[k+1],a[k+2],...,a[j])) \] 那么我们考虑另一种合并方式：\[ ((a[i],a[i+1],...,a[p])U(a[p+1],a[p+2],...,a[k]))U(a[k+1],a[k+2],...,a[j]) \] 则对应的转移方程为：\[ f[i][j]=f[i][p]+f[p+1][k]+f[k+1][j]+w[i][p]+\sum_{l=p+1}^ja[l] +w[i][j] \] 由于另一种合并方式必定比原决策更优，即选取决策点 \(k\) 优于 \(p\) ，\(k>p\) ，由于函数 \(S\) 在 \(>=0\) 右侧区间单调递增，则若选取决策点为 \(p\) 且 \(S>=0\) 且 \(p<j-1\) ，那么总有选取 \(k=s[p+1][j]>p\) 优于 \(p\) ，那么由此可知对于某个决策点 \(q\) 往右的决策必定单调变优。则对于所有 \(p>q\) ，选取 \(p=j-1\) 将会最优。- 对于 \(S<0\) ：
类似的，设最优决策点为 \(i<p<j-1\) ，我们设 \(s[i][p]=k\) ，那么对应值为：
\[ f[i][k]+f[k+1][p]+f[p+1][j]+w[i][p]+w[i][j] \] 同样，我们考虑另一种合并方式：合并 \([i,k]([k+1,p][p+1,j])\) ，则此时的值为\[ f[i][k]+f[k+1][p]+f[p+1][j]+w[p+1][j]+w[i][j]+\sum_{l=k+1}^pa[l] \] 则另一种必定优于原本的决策。那么对于上面的决策点 \(q\) 往左的决策必定单调变优，因为对于任意 \(p>i\) 且 \(S<0\) 都必定有决策点 \(k=s[i][p]<p\) 要更优，则在左端点选取 \(p=i\) 最优。
得证，故转移决策点仅需在 \(i\) 与 \(j-1\) 之间选取。
Code
重点看 \(dp\) 就好 = =。
#include#include #include using namespace std;int n, a[101], fmax[201][101], posi[201][101], fmin[201][101], maxans, minans;int main() { cin >> n; memset(fmin, 0x7f, sizeof(fmin)); minans = 2e9; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i + n] = a[i]; } for (int i = 1; i <= 2 * n; i++) a[i] += a[i - 1], fmin[i][i] = 0, posi[i][i] = i; //初始化 dp 数组与 决策点 for (int i = 1; i < n; i++) for (int j = 1; j <= 2 * n - i; j++) { fmax[j][j + i] = max(fmax[j][j + i - 1], fmax[j + 1][j + i]) + a[j + i] - a[j - 1]; //两个端点取最优 for (int k = posi[j + 1][j + i]; k >= posi[j][j + i - 1]; k--) if (fmin[j][j + i] > 0ll + fmin[j][k] + fmin[k + 1][j + i] + a[j + i] - a[j - 1]) fmin[j][j + i] = fmin[j][k] + fmin[k + 1][j + i] + a[j + i] - a[j - 1], posi[j][j + i] = k; //四边形不等式优化后的决策点枚举 } for (int i = 1; i <= n; i++) { minans = min(minans, fmin[i][i + n - 1]); maxans = max(maxans, fmax[i][i + n - 1]); } cout << minans << endl; cout << maxans;}
Example 2--山区建小学
Problem
一条直线上分布着 \(n\) 个村子 \((n\le 500)\) ，第 \(i\) 个村子距离第 \(i+1\) 个村子的距离为 \(a_i\) ，要求在 \(n\) 个村子中选取 \(m\) 个建造小学 \((m\le n)\) ，使得所有村子到距离它最近的小学的距离和最小。输出最小距离和。
First Mentality
一道很经典的 \(DP\) 题。设 \(w[i][j]\) 为在村庄 \(i-j\) 中只建立一个小学，所有村庄到这个小学的最小距离和。而这个最小距离和的位置必定为最中间的那个村庄，这也是一个经典的数学证明，即中位数为最小距离和的位置。
设 \(f[i][j]\) 为对于前 \(i\) 个村庄建立 \(j\) 个小学的最小距离和，那么转移方程为：
\[ f[i][j]=Min(f[k][j-1]+w[k+1,i]) \]\(w\) 函数只需要勤记前缀和即可转移时 \(O(1)\) 求出。不用疑惑为什么这样转移没有考虑第 \(k+1-i\) 个村庄中为什么不会有到前 \(k\) 个村庄的小学距离更短的村庄，因为这样反正不会影响答案使之变劣。
四边形不等式优化
经过大眼 or 打表观察法， 我们发现 \(w\) 函数又满足四边形不等式！那么我们假设 \(s[i][j]\) 为 \(f[i][j]\) 的最优决策点，即 \(f[i][j]=f[s[i][j]][j-1]+w[s[i][j]+1][i]\) ，我们同样可以猜想套路：
\(f[i][1]=w[1][i],s[i][1]=(i+1)>>1,s[n+1][i]=n\)
完毕。
Code
\(dp\) 才是重点，码风比较仙。
#include#include #include using namespace std;int n, m, d[501], q[501], h[502], f[501][501], pos[502][501], inf = 1e9;int work(int l, int r) { int mid = (l + r) >> 1; return h[l] - h[mid] - (mid - l) * (h[mid] - h[mid + 1]) + q[r] - q[mid] - (r - mid) * (q[mid] - q[mid - 1]);} // w 函数计算int main() { cin >> n >> m; for (int i = 2; i <= n; i++) { scanf("%d", &d[i]); q[i] = d[i], h[i - 1] = d[i]; } for (int l = 1; l <= 2; l++) for (int i = 1; i <= n; i++) q[i] += q[i - 1]; //初始化前缀和的前缀和 for (int l = 1; l <= 2; l++) for (int i = n; i >= 1; i--) h[i] += h[i + 1]; //初始化后缀和的后缀和 for (int i = 1; i <= n; i++) f[i][1] = work(1, i), pos[i][1] = 0; //初始化 dp 数组与决策点 for (int j = 2; j <= m; j++) { pos[n + 1][j] = n; for (int i = n; i > j; i--) //由于四边形不等式需要，我们从大到小枚举 i { f[i][j] = inf; for (int k = pos[i][j - 1]; k <= pos[i + 1][j]; k++) { int tmp = f[k][j - 1] + work(k + 1, i); if (tmp < f[i][j]) f[i][j] = tmp, pos[i][j] = k; } } } cout << f[n][m];}
总结
四边形不等式是一个套路，虽然不常见，但是应熟记于心以防万一。
同时，考场上要通过数学证明函数满足四边形不等式其实还是蛮困难的，建议不要头铁，打打表证明就好了= = 。