传送门：

本题是一个运动学问题——匀变速运动。

一个质点，从静止开始运动。按照速度限制，可将运动划分成n个阶段，第i个阶段的时间为t_i s，速度上限为v_i m/s。已知这个质点的加速度大小只取0或±1m/s²。以及，质点在最初和最终的时刻速度为0。求质点的最大位移。

以下变量均采用国际单位制。

对于运动某一个阶段（例如第i个阶段），可以分成三个子阶段：匀加速运动、匀速运动和匀减速运动。记三个子阶段的时间分别为inc、kep、dec，则inc+kep+dec=t[i]。记下一个阶段的限速为lim，则：

1. 匀加速阶段：inc=min{
   vi-cur,(lim+t[i]-cur)/2,t[i]}；
2. 匀减速阶段：dec=max{0,cur+inc-lim}；
3. 匀速阶段：kep=t[i]-inc-dec。

于是，分别对这三段时间计算位移，求和即可。时间复杂度为O(n²)，空间复杂度为O(n)。

参考程序如下：

#include 
     
      #define MAX_N 101double t[MAX_N], v[MAX_N];double max(double a, double b){    return a > b? a: b;}double min(double a, double b){    return a < b? a: b;}int main(void){    int n;    scanf("%d", &n);    for (int i = 0; i < n; i++)        scanf("%lf", &t[i]);    for (int i = 0; i < n; i++)        scanf("%lf", &v[i]);    double cur = 0.;    double ans = 0.;    for (int i = 0; i < n; i++) {        double inc, kep, dec;        double lim = 1.E8;        double tmp = 0.;        for (int j = i + 1; j <= n; j++) {            lim = min(lim, v[j] + tmp);            tmp += t[j];        }        inc = min(v[i] - cur, (lim + t[i] - cur) * .5);        inc = min(inc, t[i]);        dec = max(0., cur + inc - lim);        kep = t[i] - inc - dec;        ans += .5 * (cur * 2. + inc) * inc;        ans += (cur + inc) * kep;        ans += .5 * ((cur + inc) * 2. - dec) * dec;        cur += inc;        cur -= dec;    }    printf("%f\n", ans);    return 0;}
     

本题也可以从以下角度考虑：

仅考虑一个区间：若在时间区间[l,r]上的速度上限为v，则在整个时间区间[0,T]上，速度上限函数为

$$f(t)=\begin{cases} v+(l-t),0\le t<l\\v,l\le t\le r\\v+(t-r),r<t\le T\end{cases}$$

其中，$T=\sum_{i=1}^{n}t_i$。

对于阶段i，对应的时间区间为$[\sum_{j=1}^{i-1}t_j , \sum_{j=1}^{i}t_j ]$，速度上限为v_i，相应的速度上限函数记为f_i(t)。考虑所有的区间，则速度上限函数为$f(t)=\min\{t,T-t,f_{i}(t)|1\le i\le n\}$。

由于v_i、t_i均是正整数，因此可以将t轴的最小单位设置为Δt=0.5s。可以假定从0时刻开始，在每一个Δt=0.5s内，质点的加速度是恒定的。则以Δt=0.5s为单位，用f(t)刻画质点运动的v-t图像，并用加速度的限制条件修正v(t)。通过质点运动的v-t图像计算其最大位移（即v-t曲线与t轴围成的图形面积）。时间复杂度为O(nT)，空间复杂度为O(n+T)。

参考程序如下：

#include 
     
      #define MAX_N 100#define MAX_T 40000int t[MAX_N];double v[MAX_N], f[MAX_T];double min(double a, double b){    return a < b? a: b;}int main(void){    int n;    scanf("%d", &n);    for (int i = 0; i < n; i++)        scanf("%d", &t[i]);    for (int i = 0; i < n; i++)        scanf("%lf", &v[i]);    for (int i = 0; i < MAX_T; i++)        f[i] = 1.E8;    int tot = 0;    for (int i = 0; i < n; i++) {        t[i] *= 2;        for (int j = tot; j <= tot + t[i]; j++)            f[j] = min(f[j], v[i]);        tot += t[i];    }    f[0] = f[tot] = 0.;    for (int i = 1; i <= tot; i++)        f[i] = min(f[i], f[i - 1] + .5);    for (int i = tot - 1; i >= 0; i--)        f[i] = min(f[i], f[i + 1] + .5);    double ans = 0.;    for (int i = 0; i < tot; i++)        ans += .25 * (f[i] + f[i + 1]);    printf("%f\n", ans);    return 0;}