题目描述：给定一个 $n$ 次函数 $f(x)$ 形如 $a_1x^n+a_{2}x^{n-1}+......+a_{n-1}x^2+a_nx+a_{n+1} $，求 $f(x)_{\max}$，且 $x\in[l,r]$，设使得 $f(x)_{\max}$ 的 $x$ 为 $x_{\max}$。
对于一个区间 $[l,r]$ 而言，若确定使得 $f(x)$ 为最大值的 $x$ 定在 $[l,r]$ 中，则可以使用三分法求解。
将区间 $[l,r]$ 用两个点均分成三段，分别为 $l+\dfrac{r-l}{3},r-\dfrac{r-l}{3}$，设 $l_1=l+\dfrac{r-l}{3},r_1=,r-\dfrac{r-l}{3}$。
则 $f(l_1)=a_1\left(l+\dfrac{r-l}{3}\right)^n+a_2\left(l+\dfrac{r-l}{3}\right)^{n-1}+......+a_{n-1}\left(l+\dfrac{r-l}{3}\right)^2+a_n\left(l+\dfrac{r-l}{3}\right)+a_{n+1}$
即 $f(l_1)=\sum\limits_{i=1}^{n+1}a_i\left(l+\dfrac{r-l}{3}\right)^{n-i+1}$
则 $f(r_1)=a_1\left(r-\dfrac{r-l}{3}\right)^n+a_2\left(r-\dfrac{r-l}{3}\right)^{n-1}+......+a_{n-1}\left(r-\dfrac{r-l}{3}\right)^2+a_n\left(r-\dfrac{r-l}{3}\right)+a_{n+1}$
即 $f(r_1)=\sum\limits_{i=1}^{n+1}a_i\left(r-\dfrac{r-l}{3}\right)^{n-i+1}$
求出 $f(l_1)$ 和 $f(r_1)$ 后，考虑怎样移动 $l,r$：
- $f(l_1)<f(r_1)$，则 $l_1<x_{\max}$，$l$ 变为 $l_1$
反证：已知 $l_1<r_1$，若 $l_1 \ge x_{\max}$，则 $r_1 > x_{\max}$，又 $[x_{\max},r]$ 的区间中 $f_i$ 单调递减，即不可能满足前提 $f(l_1)<f(r_1)$，即假设不成立，证毕。
- $f(l_1)=f(r_1)$，此时 $l_1<x_{\max}<r_1$，$l$ 变为 $l_1$ 或 $r$ 变为 $r_1$ 都可以
证明：由于 $l_1<r_1$，即 $l_1\neq r_1$，显然 $f(l_1)=f(r_1)$ 不可能出现在 $x_{\max}$ 的同一侧，证毕。
- $f(l_1)>f(r_1)$，则 $r_1>x_{\max}$，$r$ 变为 $r_1$
反证：已知 $l_1<r_1$，若 $r_1 \le x_{\max}$，则 $l_1 < x_{\max}$，又 $[l,x_{\max}]$ 的区间中 $f_i$ 单调递增，即不可能满足前提 $f(l_1)>f(r_1)$，即假设不成立，证毕。
标签：三分法,right,dfrac,max,自学,+......+,模板,left From： https://www.cnblogs.com/CSP-AK-zyz/p/17691908.html