【bzoj3695】滑行

2015.03.26 15:39 Thu | 2次阅读 | 旧日oi | 固定链接 | 源码

Description

    首长NOI惨跪,于是去念文化课了。现在,他面对一道物理题。
现在有一个小滑块可以在地面上滑行,地面上被划分成不同的区域,使得小滑块在不同的
区域内部有一个不同的速度上限。
小滑块在(0,0)点,我们现在要推动小滑块到目标点(x,y)。
地面上有N层区域,每层区域都是矩形,现在给你一个序列{Hi}表示每层区域的高度,覆盖的地面横坐标范围是0~X,第i个区域的限速是vi。
注: Y=Sigma(Hi) 其中i从1到N
其它的地方小滑块不允许进入。
现在我们要设计一个路线使得小滑块滑到目标点的用时最小。

Input

  第一行两个整数,分别表示N、x。
第二行N个整数,第i个数表示Hi。。
第三行N个整数,第i个数表示Vi。

Output

  一行一个整数,表示最小用时,保留到小数点后第三位。

Sample Input

1 5
5
1

Sample Output

7.071

HINT

N<=100,X<=1000,对于任意i,满足1<=i<=N-1,有Vi<V(i+1)

题解

上午考试,不知道这个物理公式,写了个dp,把x乘了1000解决精度问题……结果还是全部re……这题算物理题吧……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-10
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int m;
double h[200],v[200],x;
double check(double x)
{
    double re=0;
    for(int i=1;i<=m;i++)
    {
        re+=h[i]*x/sqrt(1-x*x);
        x=x/v[i]*v[i + 1];
    }
    return re;
}
 double cost(double x)
{
    double re=0.0;
    for (int i=1;i<=m;i++)
    {
        re+=h[i]/sqrt(1-x*x)/v[i];
        x=x/v[i]*v[i+1];
    }
    return re;
}
int main()
{
    m=read();scanf("%lf",&x);
    for(int i=1;i<=m;i++) scanf("%lf",&h[i]);
    for(int i=1;i<=m;i++) scanf("%lf",&v[i]);
    double l=0,r=1;
    while (true)
    {
        double mid=(l + r) / 2;
        double p=check(mid);
        if (p<x) l=mid;
        else r=mid;
        if (fabs(cost(l)-cost(r))<1e-4)
        {
            cout<<fixed<<setprecision(3)<<cost(l)<<endl;
            return 0;
        }
    }
    return 0;
}```