P1095 守望者的逃离

P1095 守望者的逃离

题意:

一个岛上有一个人，跑步速度为 \(17m/s\) ，消耗 \(10\) 点魔法值可以在 \(1s\) 内移动 \(60m\) ，每秒原地休息的话可以恢复 \(4\) 点的魔法值。

已知这个人的魔法初始值为 \(M\) ,他所在的初始位置与岛的出口之间的举例 \(S\) ，岛沉没的时间为 \(T\) 。如果能逃出岛屿则输出逃出去需要的最短时间，否则输出能跑到的最远距离。

思路：

在每一秒我们只有三种操作，跑步，原地恢复，和施展魔法，就自然的想到是否可以使用动态规划来解决这道问题。

我们进行一种操作，需要知道当前的时间，和当前的魔法值。所以很自然的想到定义 \(f[i][j]\) 为经过了 \(i\) 秒，魔法值为 \(j\) 时可以跑到的最远距离。

分析数据范围，显然这样会 MLE 和 TLE ，所以就思考是否有地方可以进行优化。发现，跑步和施展法术都需要消耗一秒，但是施展法术获得的距离远远大于跑步，所以可以得出结论，如果我们此时可以施展法术，则一定施展法术，然后因为每次恢复速度为 \(4\) 秒，施展法术每次消耗 \(10\) 点，所以第二维度开 \(15\) 就够了。

因为这里的第二维度为 \(15\) ，所以要先预处理初始的法术值，直到这个法术值不够施展，再去 \(dp\)

实现:

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = 15, INF = 1e8;
int f[N][M];
int main()
{
    int m, s, t, tot, dist;
    scanf("%d%d%d", &m, &s, &t);
    tot = t;
    dist = s;
    int v = 17, del = 10, up = 60, rev = 4;
    int res = INF;
    // 可以施法的时候就立马施法
    while (m >= del && t)
    {
        m -= del;
        t--;
        s -= up;
        if (s <= 0)
        {
            res = tot - t;
            break;
        }
    }
    dist -= s; //预处理时已经运动的距离
    tot -= t;  //预处理时消耗的时间

    if (res != INF)
    {
        printf("Yes\n%d\n", res);
        return 0;
    }
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            f[i][j] = -INF;

    f[0][m] = 0;
    for (int i = 1; i <= t; i++)
    {
        for (int j = 0; j < M; j++)
        {
            // 选择跑步
            f[i][j] = max(f[i][j], f[i - 1][j] + v);
            if (j - rev >= 0)
                // 休息
                f[i][j] = max(f[i][j], f[i - 1][j - rev]);
            if (j + del < M)
                // run!
                f[i][j] = max(f[i][j], f[i - 1][j + del] + up);
        }
    }

    int best = 0;
    for (int i = 1; i <= t; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (f[i][j] >= s)
            {
                res = min(res, i);
            }
            best = max(best, f[i][j]);
        }
    }
    
    if (res != INF)
        printf("Yes\n%d\n", res + tot);//剩下段需要的最短时间 + 预处理耗费的时间
    else
        printf("No\n%d\n", best + dist);//剩下段能跑到的最远距离 + 预处理时跑到的距离

    return 0;
}