AtCoder Express [AtCoder Beginner Contest 076 D]

http://abc076.contest.atcoder.jp/tasks/abc076_d

解法

http://abc076.contest.atcoder.jp/submissions/1720731

DPで解く。
dp[i][v] := i番目までで速さがvの時の最大移動距離
初期値はdp[0][0] = 1としておく(dpの値が0は起こり得ない状態として、最後に答えから1引く)。
dp[i][v]からの遷移先はdp[i + 1][ [0..100] ]の101通りある。
この間での最大移動距離は、

　　　／￣￣￣￣＼
　　／
　／
／

のようになるか

　　／＼
　／　　＼
／

のようになるかの2択である。

遷移先の速さをvvとする。
まず、遷移不可能な場合はT[i] < abs(v - vv)の場合である。

a = V[i] - v
b = V[i] - vv
とすると、

a+b≦T[i]であれば、上を経由できる
この場合では、最初のa秒で限界まで加速し、限界速度で移動してから、最後のb秒で指定の速度まで減速する。
加速でup=(v+V[i])*a/2だけ移動し、限界速度でstay=V[i] * (T[i]-a-b)だけ移動し、減速でdown=(vv+V[i])*b/2だけ移動する。
up+stay+downを追加して更新する。
　
それ以外では、山を作る
加速でx秒、減速でy秒かかるとすると、
x + y = T[i]
v + x == vv + y
を満たせば良い、これを連立方程式として解くと、
x = (vv - v + T[i]) / 2
y = (T[i] - vv + v) / 2
すると、山の頂点の速さvvvはv+xとなる。
これで、加速でup=(v+vvv)*x/2だけ移動し、減速でdown=(vv+vvv)*y/2だけ移動する。
up+downを追加して更新する。
　
dp[N][0]が答え

int N, T[101], V[101];
double dp[105][105];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> T[i];
    rep(i, 0, N) cin >> V[i];
 
    dp[0][0] = 1;
    rep(i, 0, N) rep(v, 0, 105) if (dp[i][v] and v <= V[i]) {
        rep(vv, 0, 105) if(vv <= V[i]) {
            int a = V[i] - v;
            int b = V[i] - vv;
            if (a + b <= T[i]) {
                double up = 1.0 * (v + V[i]) * a / 2;
                double stay = V[i] * (T[i] - a - b);
                double down = 1.0 * (vv + V[i]) * b / 2;
                double c = up + stay + down;
                dp[i + 1][vv] = max(dp[i + 1][vv], dp[i][v] + c);
            } else if (T[i] < abs(vv - v)) {
                // can't
            } else {
                double x = 1.0 * (vv - v + T[i]) / 2;
                double y = 1.0 * (T[i] - vv + v) / 2;
                double vvv = v + x;
 
                double up = 1.0 * (v + vvv) * x / 2;
                double down = 1.0 * (vv + vvv) * y / 2;
 
                double c = up + down;
 
                dp[i + 1][vv] = max(dp[i + 1][vv], dp[i][v] + c);
            }
 
        }
    }
    printf("%.10f\n", dp[N][0] - 1);
}