壹
\(f(x_1,x_2,\dots,x_n)=(a_1,a_2,\dots,a_n)\)，要让 \(\max\{a_1,a_2,\dots,a_n\}\) 最小或 \(\min\{a_1,a_2,\dots,a_n\}\) 最大。
如果直接 DP 考虑让每一个 \(a_i\) 都尽量小，是不满足最优子结构的。如果记上 \(\max\{a_1,a_2,\dots,a_n\}\) 进行 DP，复杂度会爆炸。
二分答案 \(X\)，DP 让每一个 \(a_i\) 尽量小，但是在 DP 的过程中让不满足 \(a_i\le X\) 的状态不进行转移。子结构间互不影响，转移到父结构的子结构都满足 \(a_i\le X\) 的限制，DP 正确性就有保证了。
贰
求满足函数 \(f(x_1,x_2,\dots,x_n,T)\ge X\) 成立的 \(T\) 的最小值。
\(T\) 的值域极大，状态记下 \(T\) 就没法 DP。如果二分答案 \(T\)，限制就变成了判断 \(f_T(x_1,x_2,\dots,x_n)\ge X\) 是否成立。
标签：二分,dots,两种,子结构,ge,答案,DP From： https://www.cnblogs.com/huaruoji/p/16804920.html