【区间 dp】UVA1331 最大面积最小的三角剖分 Minimax Triangulation 题解-526互联

区间 dp。

有一个很经典的问题：给定一个凸多边形，求它的最优三角剖分，对每个三角形规定一个权函数 \(f(i,j,k)\)，求所有剖分方案中最大的权值。

发现这个东西不好直接入手。但是这个东西与矩阵最优链乘是相似的。考虑区间 dp。因为随意的转移是难以维护的，维护区间信息就等于强制的规定了一个转移顺序，这样就可以很方便的转移了。

在回到本题。如果加上凸多边形的限制，就很容易了。

令 \(f_{i, j}\) 表示多边形 \(i, i+1, \dots,j\) 的最优解，容易得到转移方程：\(f_{i, j} = \min\limits_{k=i+1}^{j-1}\{\max(f_{i, k}, f_{k, j}, S(i, j, k))\}\)，其中 \(S(i, j, k)\) 表示点 \(i, j, k\) 的面积。

由于本题要求对角线 \(i-j\) 在多边形内，赋一个极大值即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ldb long double
#define vi vector < int >
#define eb emplace_back
#define pii pair < int, int >
#define fi first
#define se second
mt19937_64 rng(35);
constexpr int N = 55;
constexpr ldb eps = 1e-9;
int n;
pii p[N];
ldb f[N][N];
ldb sqr(ldb a) {
	return a * a;
}
ldb dis(pii &a, pii &b) {
	return sqrt(sqr(a.fi - b.fi) + sqr(a.se - b.se));
}
ldb area(pii &a, pii &b, pii &c) {
	ldb x = dis(a, b), y = dis(b, c), z = dis(c, a);
	ldb p = (x + y + z) / 2;
	return sqrt(p * (p - x) * (p - y) * (p - z));
}
bool check(int a, int b, int c) {
	pii x = p[a], y = p[b], z = p[c];
	ldb s = area(x, y, z);
	for(int i = 1; i <= n; ++i) {
		if(i == a || i == b || i == c) continue;
		if(fabs(s - area(x, y, p[i]) - area(x, p[i], z) - area(p[i], y, z)) < eps)
			return 0;
	}
	return 1;
}
void solve() {
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> p[i].fi >> p[i].se;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			f[i][j] = 1e18;
	for(int i = 1; i < n; ++i) f[i][i + 1] = 0;
	for(int i = 1; i < n - 1; ++i) f[i][i + 2] = area(p[i], p[i + 1], p[i + 2]);
	for(int len = 3; len <= n; ++len) {
		for(int i = 1; i <= n - len + 1; ++i) {
			int j = i + len - 1;
			for(int k = i + 1; k < j; ++k)
				if(check(i, j, k))
					f[i][j] = min(f[i][j], max(max(f[i][k], f[k][j]), area(p[i], p[j], p[k])));
		}
	}
	cout << fixed << setprecision(1) << f[1][n] << "\n";
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--) solve(); 
	return 0;
}

顺便再提供一组样例：