Triangulation

UVA1331 区间 dp。 有一个很经典的问题：给定一个凸多边形，求它的最优三角剖分，对每个三角形规定一个权函数 \(f(i,j,k)\)，求所有剖分方案中最大的权值。 发现这个东西不好直接入手。但是这个东西与矩阵最优链乘是相似的。考虑区间 dp。因为随意的转移是难以维护的，维护区间信息就等于强制 ......