bzoj2876 [NOI2012]骑行川藏

ShinriiTin posted @ 2015年6月11日 16:17 in 未分类 with tags 拉格朗日乘数法 , 452 阅读

求条件极值 min f(x)=∑_is_i/x_i,g(x)=E-∑_i k_i*(x_i-v_i)²*s_i=0

构造拉格朗日函数L(x)=f(x)-λ*g(x),λ为拉格朗日乘数

则有f(x)取极值时,有L_xi(x)=0,g(x)=0

二分λ,解方程L_xi(x)=2*λ*k_i*s_i*(x_i-v_i)-s_i/x_i²=0再带入g(x)=0中去验证

整理得:2*λ*k_i*x_i²*(x_i-v_i)=1

看起来，这个方程似乎不太好解。。。

题目中还蕴含一个条件:x_i>v_i且x_i>0，我们总不能倒着走对吧。。。

所以，这个函数在满足题意的定义域内单调，就可以二分求解了

My Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64	`#include <stdio.h>` `#include <string.h>` `#include <algorithm>` `#define eps 1e-12` `#define inf 1e12` `using` `namespace` `std;` `const` `int` `MAXN=10005;` `typedef` `long` `double` `db;` `int` `n;` `db x[MAXN];` `double` `s[MAXN],k[MAXN],v[MAXN],E;` `db ans;` `inline` `db equation(int` `i){` `db l=max(0.,v[i]),r=inf;` `while(r-l>eps){` `db m=(l+r)/2.;` `if(ans2.k[i](m-v[i])mm-1.>0)r=m;` `else` `l=m;` `}` `return` `l;` `}` `inline` `db phi(){` `db res=0;` `for(int` `i=1;i<=n;++i)` `res+=k[i]s[i](x[i]-v[i])(x[i]-v[i]);` `return` `res-E;` `}` `inline` `db calc(){` `db res=0;` `for(int` `i=1;i<=n;++i)` `res+=s[i]/x[i];` `return` `res;` `}` `inline` `void` `Init(){` `scanf("%d%lf",&n,&E);` `for(int` `i=1;i<=n;++i)` `scanf("%lf%lf%lf",s+i,k+i,v+i);` `}` `inline` `void` `Solve(){` `db l=0,r=inf;` `while(r-l>eps){` `ans=(l+r)/2.;` `for(int` `i=1;i<=n;++i)` `x[i]=equation(i);` `if(phi()>eps)l=ans;` `else` `r=ans;` `}` `ans=calc();` `printf("%.8f\n",(double)ans);` `}` `int` `main(){` `Init(); Solve();` `return` `0;` `}`