在省赛的时候没有开这题,结束后发现这居然是个线性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作为起点,在这个点他可以上升到任意高度.求林克从初始位置到达终点位置所用的最短时间.
题解
对比两种飞行方式:
- 在一个点先上升到特定高度,这个高度刚好满足从当前点到下一个点的距离除以下落时间.那么总时间就是上升到特定高度的时间s_1, 加上水平方向移动的时间s_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;
}