差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:2sozx:数学:知识点 [2020/05/15 15:26]
2sozx [拉格朗日乘子法]
+++ 2020-2021:teams:farmer_john:2sozx:数学:知识点 [2020/06/12 22:13] (当前版本)
2sozx [NOI2012骑行川藏]
@@ 行 1: / 行 1: @@
+**格式**：
+  - 向量建议写成 $\boldsymbol{x}_{0}$
+**内容**：
+  - 没有例题吗
 =====知识点=====
 ====前言====
@@ 行 5: / 行 11: @@
 对于没有限制条件的多元函数来说，只需要对函数求导即可，但是若有了限制条件，即函数的值要在一定条件下才能取到，则需要用到拉格朗日乘子法。
-====前置知识====
-多元函数的求导\\
-多元函数极值的概念\\
-二次型矩阵
 ====引理====
-设函数 $f(\vec{x})$ ，${\vec{\varphi}}(\vec{x})=({\varphi}_1(\vec{x}),{\varphi}_2(\vec{x}),…,{\varphi}_m(\vec{x}))$ 在区域 $D\subset \mathbb{R}^n (m<n)$ 内具有各个连续偏导数，再设 ${\vec{x_0}}=({x_1}^0,{x_2}^0,…,{x_n}^0)\in D$ 为$f(\vec{x})$ 在约束条件 $$\begin{cases}{\varphi}_1(\vec{x})=0 \\{\varphi}_2(\vec{x})=0 \\…\\{\varphi}_m(\vec{x})=0\end{cases}$$下的极值点，并且 ${\varphi}'(x_0)$ 的秩为 $m$ ，则存在常数 ${\lambda}_1,{\lambda}_2,…,{\lambda}_3{\in}\mathbb{R}$ ，使得在 $\vec{x_0}$ 处成立下述等式：$$\begin{cases}{\frac{\partial{f(\vec{x_0})}}{\partial{x_i}}}+\sum_{j=1}^m {\lambda}_j \frac{\partial{\varphi}_j(\vec{x_0})}{\partial{x_i}}=0\quad (i=1,2,…,n) \\ \\ {\varphi}_j(\vec{x_0})=0\qquad\qquad\qquad\qquad  (j=1,2,…,m)\end{cases}$$
+设函数 $f(\boldsymbol{x})$ ，${\boldsymbol{\varphi}}(\boldsymbol{x})=({\varphi}_1(\boldsymbol{x}),{\varphi}_2(\boldsymbol{x}),\cdots,{\varphi}_m(\boldsymbol{x}))$ 在区域 $D\subset \mathbb{R}^n (m<n)$ 内具有各个连续偏导数，再设 ${\boldsymbol{x_0}}=({x_1}^0,{x_2}^0,\cdots,{x_n}^0)\in D$ 为$f(\boldsymbol{x})$ 在约束条件 $$\begin{cases}{\varphi}_1(\boldsymbol{x})=0 \\{\varphi}_2(\boldsymbol{x})=0 \\ \vdots\\{\varphi}_m(\boldsymbol{x})=0\end{cases}$$下的极值点，并且 ${\varphi}'(x_0)$ 的秩为 $m$ ，则存在常数 ${\lambda}_1,{\lambda}_2,\cdots,{\lambda}_3{\in}\mathbb{R}$ ，使得在 $\boldsymbol{x_0}$ 处成立下述等式：$$\begin{cases}{\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_i}}}+\sum_{j=1}^m {\lambda}_j \frac{\partial{\varphi}_j(\boldsymbol{x_0})}{\partial{x_i}}=0\quad (i=1,2,\cdots,n) \\ \\ {\varphi}_j(\boldsymbol{x_0})=0\qquad\qquad\qquad\qquad  (j=1,2,\cdots,m)\end{cases}$$
 ====证明====
-由于 ${\varphi'(\vec{x_0})}$ 的秩为 $m$ ，我们不妨设行列式$$\frac{\partial(\varphi_1,\varphi_2,…,\varphi_m)}{\partial(x_{n-m+1},x_{n-m+2},…,x_n)}$$在 $x_0$ 处不为零。
+由于 ${\varphi'(\boldsymbol{x_0})}$ 的秩为 $m$ ，我们不妨设行列式$$\frac{\partial(\varphi_1,\varphi_2,\cdots,\varphi_m)}{\partial(x_{n-m+1},x_{n-m+2},\cdots,x_n)}$$在 $x_0$ 处不为零。
-因此，在 $\vec{x_0}$ 的某个邻域内唯一确定一组具有各个连续偏导数的隐函数$$\begin{cases}x_{n-m+1}=g_1(x_1,x_2,…,x_{n-m}),\\ x_{n-m+2}=g_2(x_1,x_2,…,x_{n-m}),\\ ……\\ x_{n}=g_m(x_1,x_2,…,x_{n-m}),\\\end{cases}$$满足 ${x_j}^0=g_j({x_1}^0,{x_2}^0,…,{x_n}^0)(j=n-m+1,n-m+2,…,n)$ 且有$$\varphi_k(x_1,…,x_{n-m},g_1(x_1,x_2,…,x_{n-m}),…,g_m(x_1,x_2,…,x_{n-m}))=0$$
+因此，在 $\boldsymbol{x_0}$ 的某个邻域内唯一确定一组具有各个连续偏导数的隐函数$$\begin{cases}x_{n-m+1}=g_1(x_1,x_2,\cdots,x_{n-m}),\\ x_{n-m+2}=g_2(x_1,x_2,\cdots,x_{n-m}),\\ \vdots\\ x_{n}=g_m(x_1,x_2,\cdots,x_{n-m}),\\\end{cases}$$满足 ${x_j}^0=g_j({x_1}^0,{x_2}^0,\cdots,{x_n}^0)(j=n-m+1,n-m+2,\cdots,n)$ 且有$$\varphi_k(x_1,\cdots,x_{n-m},g_1(x_1,x_2,\cdots,x_{n-m}),\cdots,g_m(x_1,x_2,\cdots,x_{n-m}))=0$$
-将隐函数组代入 $f(\vec{x_0})$ 得$$f(x_1,…,x_{n-m},g_1(x_1,x_2,…,x_{n-m}),…,g_m(x_1,x_2,…,x_{n-m}))$$
+将隐函数组代入 $f(\boldsymbol{x_0})$ 得$$f(x_1,\cdots,x_{n-m},g_1(x_1,x_2,\cdots,x_{n-m}),\cdots,g_m(x_1,x_2,\cdots,x_{n-m}))$$
-因此， $\vec{x_0}$ 是条件极值点转化为 $({x_1}^0,{x_2}^0,…,{x_{n-m}}^0)$ 为上述函数的通常极值点。\\
+因此， $\boldsymbol{x_0}$ 是条件极值点转化为 $({x_1}^0,{x_2}^0,\cdots,{x_{n-m}}^0)$ 为上述函数的通常极值点。\\
-令 $\vec{x_0}'$ 则对 $i=1,2,…n-m$ 有$$\frac{\partial{f(\vec{x_0})}}{\partial{x_i}}+\frac{\partial{f(\vec{x_0})}}{\partial{x_{n-m+1}}}{\cdot}\frac{\partial{g_1(\vec{x_0}')}}{\partial{x_i}}+…+\frac{\partial{f(\vec{x_0})}}{\partial{x_n}}{\cdot}\frac{\partial{g_m(\vec{x_0}')}}{\partial{x_i}}=0$$
+令 $\boldsymbol{x_0}'$ 则对 $i=1,2,\cdots,n-m$ 有$$\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_i}}+\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}}{\cdot}\frac{\partial{g_1(\boldsymbol{x_0}')}}{\partial{x_i}}+\cdots+\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_n}}{\cdot}\frac{\partial{g_m(\boldsymbol{x_0}')}}{\partial{x_i}}=0$$
-令 $\vec{g}(\vec{x}'=(g_1(\vec{x}'),g_2(\vec{x}'),…,g_m(\vec{x}'))^T$ ，其中 $\vec{x}'=(x_1,x_2,…,x_{n-m})$。将上述 $n-m$ 个等式写成向量形式，有$$\left(\frac{\partial{f(\vec{x_0})}}{\partial{x_1}},…,\frac{\partial{f(\vec{x_0})}}{\partial{x_{n-m}}}\right)+\left(\frac{\partial{f(\vec{x_0})}}{\partial{x_{n-m+1}}},…,\frac{\partial{f(\vec{x_0})}}{\partial{x_n}}\right)\vec{g}(\vec{x_0}')=0\quad \left(1\right)$$
+令 $\boldsymbol{g}(\boldsymbol{x}'=(g_1(\boldsymbol{x}'),g_2(\boldsymbol{x}'),\cdots,g_m(\boldsymbol{x}'))^T$ ，其中 $\boldsymbol{x}'=(x_1,x_2,\cdots,x_{n-m})$。将上述 $n-m$ 个等式写成向量形式，有$$\left(\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_1}},\cdots,\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\right)+\left(\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}},\cdots,\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_n}}\right)\boldsymbol{g}(\boldsymbol{x_0}')=0\quad \tag{1}$$
-由于$$\vec{g}(\vec{x_0}')=-\left(\begin{array} {}\frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_n}}\\ \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_n}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_n}}\end{array}\right)^{-1}
+由于$$\boldsymbol{g}(\boldsymbol{x_0}')=-\left(\begin{array} {}\frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_n}}\\ \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_n}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_n}}\end{array}\right)^{-1}
-\left(\begin{array} {}\frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_{n-m}}}\\ \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_{n-m}}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_{n-m}}}\end{array}\right)\triangleq -A^{-1}B\quad \left(2\right)$$
+\left(\begin{array} {}\frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\\ \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\end{array}\right)\triangleq -A^{-1}B\quad \tag{2}$$
-注意到$$-\left(\frac{\partial{f(\vec{x_0})}}{\partial{x_{n-m+1}}},…,\frac{\partial{f(\vec{x_0})}}{\partial{x_n}}\right)\cdot A^{-1}$$
+注意到$$-\left(\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}},\cdots,\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_n}}\right)\cdot A^{-1}$$
-是一个 $m$ 维行向量，我们可以将其记为$$-\left(\frac{\partial{f(\vec{x_0})}}{\partial{x_{n-m+1}}},…,\frac{\partial{f(\vec{x_0})}}{\partial{x_n}}\right)\cdot A^{-1}=\left(\lambda_1,\lambda_2,\cdots,\lambda_m\right)\quad \left(3\right)$$
+是一个 $m$ 维行向量，我们可以将其记为$$-\left(\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}},\cdots,\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_n}}\right)\cdot A^{-1}=\left(\lambda_1,\lambda_2,\cdots,\lambda_m\right)\quad \tag{3}$$
 将 $\left(2\right),\left(3\right)$代入之前的式子 $\left(1\right)$ 得
-$$\left(\frac{\partial{f(\vec{x_0})}}{\partial{x_1}},…,\frac{\partial{f(\vec{x_0})}}{\partial{x_{n-m}}}\right)+\left(\lambda_1,\lambda_2,\cdots,\lambda_m\right)\left(\begin{array} {}\frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_{n-m}}}\\ \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_{n-m}}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_{n-m}}}\end{array}\right)=0\quad \left(4\right)$$
+$$\left(\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_1}},\cdots,\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\right)+\left(\lambda_1,\lambda_2,\cdots,\lambda_m\right)\left(\begin{array} {}\frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\\ \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_1}} & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_2}} & \cdots & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_{n-m}}}\end{array}\right)=0\quad \tag{4}$$
 另外我们可以将 $\left(3\right)$ 改写成
-$$ \left(\frac{\partial{f(\vec{x_0})}}{\partial{x_{n-m+1}}},…,\frac{\partial{f(\vec{x_0})}}{\partial{x_n}}\right)+\left(\lambda_1,\lambda_2,\cdots,\lambda_m\right)\left(\begin{array} {}\frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_1(\vec{x_0})}}{\partial{x_n}}\\ \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_2(\vec{x_0})}}{\partial{x_n}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_m(\vec{x_0})}}{\partial{x_n}}\end{array}\right)=0\quad \left(5\right)$$
+$$ \left(\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}},\cdots,\frac{\partial{f(\boldsymbol{x_0})}}{\partial{x_n}}\right)+\left(\lambda_1,\lambda_2,\cdots,\lambda_m\right)\left(\begin{array} {}\frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_1(\boldsymbol{x_0})}}{\partial{x_n}}\\ \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_2(\boldsymbol{x_0})}}{\partial{x_n}}\\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_{n-m+1}}} & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_{n-m+2}}} & \cdots & \frac{\partial{\varphi_m(\boldsymbol{x_0})}}{\partial{x_n}}\end{array}\right)=0\quad \tag{5}$$
 将 $\left(4\right),\left(5\right)$ 写成分量形式再加上约束条件即可证明。
 =====拉格朗日乘子法=====
-构造函数 $F(x_1,\cdots,x_n,\lambda_1,\cdots,\lambda_m)=f(\vec{x})+\sum_{j=1}^m \lambda_j\varphi_j(\vec{x})$ ，则上述求条件极值点的必要条件形式转化为 $F$ 的通常极值的必要条件 $$\begin{cases}\frac{\partial{F(\vec{x_0})}}{\partial{x_i}}=0\quad(i=1,2,\cdots,n)\\ \frac{\partial{F(\vec{x_0})}}{\partial{\lambda_j}}=0\quad(j=1,2,\cdots,m)\end{cases}$$
+构造函数 $F(x_1,\cdots,x_n,\lambda_1,\cdots,\lambda_m)=f(\boldsymbol{x})+\sum_{j=1}^m \lambda_j\varphi_j(\boldsymbol{x})$ ，则上述求条件极值点的必要条件形式转化为 $F$ 的通常极值的必要条件 $$\begin{cases}\frac{\partial{F(\boldsymbol{x_0})}}{\partial{x_i}}=0\quad(i=1,2,\cdots,n)\\ \frac{\partial{F(\boldsymbol{x_0})}}{\partial{\lambda_j}}=0\quad(j=1,2,\cdots,m)\end{cases}$$
 此即拉格朗日乘子法
+=====例题=====
+====CF813C====
+  * 题意：给定整数 $a,b,c,s$ ，求使得 $x^ay^bz^c$ 最大的实数 $x,y,z$ ，其中 $x+y+z\le s(1\le s \le 10^3,0\le a,b,c \le 10^3)$
+  * 题解:对于 $x,y,z > 0$ 时显然取 $x+y+z=s$ 时会比 $x+y+z<s$ 时更优；对于 $xyz=0$ 时取 $x+y+z=s$ 不会比 $x+y+z<s$ 劣。因此可以将限制条件改为 $x+y+z=s$ 即可。令 $G(x,y,z)=x+y+z-s，F(x,y,z)=a\ln x+b\ln y+c\ln z，H(x,y,z)=F(x,y,z)+\lambda G(x,y,z)$ 套用拉格朗日乘子法即可得到 $$x=\frac{as}{a+b+c},y=\frac{bs}{a+b+c},z=\frac{cs}{a+b+c}$$ 注意 $a+b+c=0$ 时需要特判。
+  * 对于所求表达式为乘积的形式时，可以取对数，如上题中 $F(x,y,z)=a\ln x+b\ln y+c\ln z$ ，此时求出的极值点依旧为原表达式的极值点，具体问题需要具体分析。
+  * 一般来说使用拉格朗日乘子法时需要注意边界条件，此题 $x,y,z$ 为边界条件时表达式值一定不会优于最大值，所以可以不考虑边界。注意边界值并不是 $0$。
+====一道没有来源的题目====
+  * 题意：平面上有$n(n{\le}8)$个点，告诉你每个点距离原点的距离,求这$n$个点所围成的凸包的最大面积
+  * 题解：枚举哪些点在凸包上,并且这些点极角排序后的顺序。假设极径依次为$r_1,r_2,⋯,r_n$。\\ 面积$S={\frac{1}{2}}(r_1r_2sinθ_1+r_2r_3sinθ_2+⋯+r_nr_1sinθ_n)$并且${\sum_{i=1}^n}{\theta}_i=2\pi$。\\ 令$F(θ_1,θ_2,⋯,θ_n)=S+{\lambda}g(θ_1,θ_2,⋯,θ_n)$,其中$g(θ_1,θ_2,⋯,θ_n)={\sum_{i=1}^n}{\theta}_i-2\pi$.\\ 由拉格朗日乘子法，解得$−λ=r_1r_2cosθ_1=r_2r_3cosθ_2=⋯=r_nr_1cosθ_n$,可二分$λ$,求出满足$g=0$的解，此时对应的$\theta$就是当前条件下面积的最大值。
+  * 注：其实枚举点在凸包上时这些点并非一定会构成凸包，但是这样的面积一定不会是最大的，对于答案并没有影响。
+  * 这道题是同学出的，并没有具体数据。
+====NOI2012骑行川藏====
+  * 题意：$n$ 段路，每段路有三个参数 $s_i,k_i,v_i'$,其中 $s_i $ ，表示这段路的长度，$k_i$ ，表示这段路的风阻系数，$v_i'$ 表示这段路上的风速。若在一段路上的速度为 $v_i$ ，消耗的能量为 $E_i=k_i(v_i-v_i')^2s_i$。初始有体能值 $E_U$ 问在有限的体力内到达目的地的最短时间是多少。
+  * 题解：显然体能值要尽量用光会更优。若 $v_i<v_i'$ 则取 $V=2v_i'-v_i$ ，两个速度消耗的能量是相同的，而且 $V$ 优于 $v_i$ ，因此我们可以默认一段路的 $v_i\ge v_i'$。题目即求在 $\sum_{i=1}^{n}E_i=E_U$ 的条件下 $T=\sum_{i=1}^{n}\frac{s_i}{v_i}$ 的最小值。套用拉格朗日乘子法可知 $$\lambda=\frac{1}{2k_i v_i (v_i-v_i')^2}$$ 根据假设 $v_i\ge v_i'$ 可知 $\frac{1}{2k_i v_i (v_i-v_i')^2}$ 单调，因此可以通过二分 $\lambda$ 来求解答案。

CVBB ACM Team

用户工具

站点工具

差别

页面工具