「GOI-R1」 不卜庐 官方题解

虚空星胜 · 2022-08-21 11:17:59 · 个人记录

不卜庐 官方题解

题意描述： 在一个平面直角坐标系中，起点为 (x_s, y_s)，终点为 (x_t, y_t)，你只能够向上下左右移动，初始时速度为 0。在起点和其他 n 个位置可以使用一次道具使得速度增加一，但是在同一个位置不能连续使用道具，只有在另一个地点使用过道具之后才能够回到当前地点再次使用道具。求从起点到终点的最短时间。

思路：

容易看出对答案有贡献的点就只有所有道具。由于我们不知道答案到底用了几次道具，因而可以列举我们到达某个点使用i次道具花费的时间。

起点的道具必须用，因此可以直接跳过。我们将起点道具以及另外n个道具处重新标点为点1到点n + 1。令dp[i][j]表示到达第i个点，除起点外使用了j个道具所花的时间。因为速度越快越好，所以到达一个道具处使用该道具一定不会让结果更差。即对于dp[i][j]，在i点我们是一定使用了i号道具的，dp[i][j]的意义变为表示到达第i个点并使用了i号道具，除起点外使用了j个道具所花的时间。则可以推得对于一个点i与另外一个转移过去的点k有转移方程如下：

其中len(i, k)表示点i到点k的距离。意思就是我们可以从k号道具的位置来到i号道具的位置，再使用i号道具加速。代码实现上，先列举道具使用次数，再进行更新。时间复杂度为O(n^2m)。

代码如下：

#include <iostream>
#include <cmath>

using namespace std;

const int N = 510;
const int K = 110;

int n, m, s, t, x, y;
double ans, dp[N][K];
struct node {
    int a, b;
}p[N];

int len(int a, int b) {
    return abs(p[a].a - p[b].a) + abs(p[a].b - p[b].b);
}

int main() {
    for (int i = 0; i <= 509; i ++)
        for (int j = 0; j <= 109; j ++)
            dp[i][j] = 1e6;//初始化 

    scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &x, &y);

    m --;//起点道具必须使用，否则无法移动 

    p[0].a = x, p[0].b = y, p[1].a = s, p[1].b = t;//重新标点并把终点存储在0号下标处 
    for (int i = 2; i <= n + 1; i ++) scanf("%d%d", &p[i].a, &p[i].b);
    n ++;

    dp[1][0] = 0, ans = len(0, 1);//也可以不使用其它道具直接到达终点 
    for (int i = 2; i <= n; i ++) dp[i][0] = len(1, i);//因为速度为1，不使用道具时间花费即为距离 
    for (int r = 1; r <= m; r ++) {//列举使用道具次数 
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (i == j) continue;
                dp[i][r] = min(dp[i][r], dp[j][r - 1] + (double)len(i, j) / r);//转移 
            }
            ans = min(ans, dp[i][r] + (double)len(0, i) / (r + 1));//更新答案 
        }
    }

    printf("%.12lf", ans);

    return 0;
}