[BZOJ2876]骑行川藏

以前并没有发现微积分教材上有这种东西...我还是太菜了...

其实就是要在满足$\sum\limits_{i=1}^nk_is_i(v_i-v_i')^2\leq E$的同时求$\sum\limits_{i=1}^n\dfrac{s_i}{v_i}$的最小值

首先我们要跑得尽可能快，所以$v_i\geq v_i'$，而且在最优解体能是一定会被用完的，那么限制就变成等式了

拉格朗日乘数法可用于求多元函数的带限制极值：$g(x_1,\cdots,x_n)=0$，求$f(x_1,\cdots,x_n)$的极值

我看的书上有一个挺好的几何解释：把$f$的图像画出来，再在上面画一些“等高线”，同时把$g(x_1,\cdots,x_n)=0$和$f(x_1,\cdots,x_n)$的“交线”画出来，那么取到极值的地方就是等高线与交线相切的地方

比如说求$f(x,y)=x^2+y^2+2$在限制$g(x,y)=x^2+\dfrac14y^2-1=0$下的极值，三张图一目了然

黄色：$z=f(x,y)$，红色：$g(x,y)=0$

$z=2$

$z=6$

相切意味着梯度线性相关，即是说如果在$x_i=t_i$处$f$取得极值，那么$\nabla f(t_1,\cdots,t_n)=\lambda\nabla g(t_1,\cdots,t_n)$，我们把它拆分成关于每个变量的偏导，即对于$\forall1\leq i\leq n$有$\left.\dfrac{\partial f}{\partial x_i}\right|_{x_i=t_i}=\lambda\left.\dfrac{\partial g}{\partial x_i}\right|_{x_i=t_i}$

再加上$g(t_1,\cdots,t_n)=0$，总共$n+1$个变量和$n+1$条方程，可以解出来

再看这道题，限制条件是$\sum\limits_{i=1}^nk_is_i(v_i-v_i')^2-E=0$，我们要求$\sum\limits_{i=1}^n\dfrac{s_i}{v_i}$的极值，所以有方程$-\dfrac1{v_i^2}=2\lambda k_i(v_i-v_i')$，首先这说明$\lambda\lt0$，方程左边是经过三四象限的类双曲线，右边是斜率为负的经过第一象限的直线，所以当$\lambda$确定后有且只有一个$v_i$满足方程，并且因为$\lambda$越大，$v_i$也越大，这直接导致了$\sum\limits_{i=1}^nk_is_i(v_i-v_i')^2$变大，所以我们可以二分出满足关于$E$的限制的$\lambda$，在这个过程中求$v_i$也是可以二分的，于是我们就愉悦地做完了这题

注意精度...

#include<stdio.h>
typedef double du;
const du eps=1e-14,inf=1e9;
du s[10010],k[10010],v[10010];
int n;
du sqr(du x){return x*x;}
du calc(int i,du lm){
	du l,r,mid;
	l=eps;
	r=inf;
	while(r-l>eps){
		mid=(l+r)*.5;
		if(-1<2*lm*k[i]*(mid-v[i])*sqr(mid))
			l=mid;
		else
			r=mid;
	}
	return mid;
}
du check(du lm){
	int i;
	du r=0;
	for(i=1;i<=n;i++)r+=k[i]*s[i]*sqr(calc(i,lm)-v[i]);
	return r;
}
int main(){
	int i;
	du E,l,r,mid,ans;
	scanf("%d%lf",&n,&E);
	for(i=1;i<=n;i++)scanf("%lf%lf%lf",s+i,k+i,v+i);
	l=-inf;
	r=-eps;
	while(r-l>eps){
		mid=(l+r)*.5;
		if(check(mid)<E)
			l=mid;
		else
			r=mid;
	}
	ans=0;
	for(i=1;i<=n;i++)ans+=s[i]/calc(i,mid);
	printf("%.10lf",ans);
}

巴特西

[BZOJ2876]骑行川藏

最新文章

热门文章