G. Gliding 2020浙江省省赛动态规划

在省赛的时候没有开这题,结束后发现这居然是个线性DP,写了写一发过了…遗憾遗憾.G. Gliding

题目大意

林克在初始位置(s_x,s_y,0)需要到达终点位置(t_x,t_y,0).他只能通过飞行到达目的地,并且有三个参数v_f直接下落的速度,v_p打开滑翔伞后的下落速度,v_h在水平移动时的速度.注意在水平移动时,垂直方向的下落速度为v_p.在一些特定的坐标有风,提供一个上升速度v_i,根据v_i – v_p的大小来决定在这个特定位置i上他是上升还是下降还是不变.林克会选择一个特殊的点(s_x,s_y,0)拥有大于v_p的v_0作为起点,在这个点他可以上升到任意高度.求林克从初始位置到达终点位置所用的最短时间.

题解

对比两种飞行方式:

1. 在一个点先上升到特定高度,这个高度刚好满足从当前点到下一个点的距离除以下落时间.那么总时间就是上升到特定高度的时间s_1, 加上水平方向移动的时间s_2.

2. 在一个点上升到一个高度,这个高度会满足后续的几个点(2\leq)的移动,那么总时间就是上升到这个高度的时间s_1机上后续几个点移动的时间s_2,其中s_2又是分段进行计算的.

根据三角形法则可以知道第一种方案是优于第二种方案的.于是就可以开始考虑状态转移方程了.

首先建立数组a_0 \rightarrow a_{n+1},其中a_0就是初始点(s_x,s_y,v_0),a_{n+1}是终点(t_x,t_y,0)并将a_1到a_n的点按照上升速度进行从小到大的排序.

对a_1到a_{n+1}中的每一个点进行初始化计算,也就是计算a_0到a_i的时间,按照第一种飞行方式的规则计算s_1+s_2.

两层嵌套计算从初始点到终点的最短用时,两段时间的计算方式如下:

double s1 = sqrt(pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2)) / vh;

double s2 = s1 * vp * 1.0 / (a[j].v - vp);

注意判断v_p与v_i的关系有:

• dp_i = min(dp_i, dp_j + s_1 + s_2)

• dp_i = min(dp_i, \infty)

参考实现

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int sx, sy, tx, ty;
int vf, vp, vh;
int t, n;

double dp[4010], ans[4010];

struct node
{
    int x, y, v;
} a[4010];

bool cmp(node a, node b)
{
    return a.v < b.v;
}

int main()
{
    scanf("%d", &t);
    while (t --)
    {
        scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
        scanf("%d %d %d", &vf, &vp, &vh);
        scanf("%d", &n);
        for (int i = 0; i <= n; i ++)
            scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].v);
        a[n+1].x = tx; a[n+1].y = ty; a[n+1].v = 0;
        // a[0].x = sx; a[0].y = ty; a[0].v = 0;
        sort(a + 1, a + 1 + n, cmp);
        memset(dp, INF, sizeof(dp));
        for (int i = 1; i <= n + 1; i ++)
        {
            double s1 = sqrt(pow(a[i].x - a[0].x, 2) + pow(a[i].y - a[0].y, 2)) / vh;
            double s2 = s1 * vp * 1.0 / (a[0].v - vp);
            dp[i] = s1 + s2;
        }

        for (int i = 1; i <= n + 1; i ++)
        {
            for (int j = 0; j <= n + 1; j ++)
            {
                if (i == j) continue;
                if (a[j].v > vp)
                {
                    double s1 = sqrt(pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2)) / vh;
                    double s2 = s1 * vp * 1.0 / (a[j].v - vp);
                    dp[i] = min(dp[i], dp[j] + s1 + s2);
                }
                else dp[i] = min(dp[i], 1.0 * INF);
            }
        }
        printf("%.15lf\n", dp[n + 1]);
    }
    return 0;
}