Minimax

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

[P5298 [PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298) ## 前言 顺着线段树合并的标签找到这道题，感觉可做，但一写写了整整一天/kk。 ## 题意 给出一个以 $1$ 为根的 $n$ 个节点的二叉树，每个叶子上有一个权值 ......