1108: 守望者的逃离

解题思路:

算是动态规划，但贪心一样可以做，就是蓝够就用闪烁，蓝不够就根据剩余蓝量、剩余时间、剩余距离决定是跑步还是闪烁。

核心思想总结来说就是：每秒的当前总位移是选择闪烁（分为位移和休息）和选择跑步两者间的最大值。

注意事项:

需要理解的地方是：blink[i] = blink[i - 1] + 60; 和 move[i] = maxLen[i - 1] + 17;前者是不能基于前一秒的最优解的，因为动态规划无法保证局部最优解。但跑步的话是可以随时基于前一秒的最优解开跑的，不管前一秒是闪烁还是休息还是跑步。正是这里卡了我半天。

参考代码:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int M = 0; // 守望者的魔法初值
    int S = 0; // 守望者所在的初始位置与岛的出口之间的距离
    int T = 0; // 岛沉没的时间
    cin >> M >> S >> T; // 读输入
    
    int move[T + 1] = { 0 }; // 当前这一秒选择跑步后的总位移
    int blink[T + 1] = { 0 }; // 当前这一秒选择闪烁后的总位移
    int maxLen[T + 1] = { 0 }; // 当前这一秒总位移的最优解
    for (int i = 1; i < T + 1; i++) {
        move[i] = maxLen[i - 1] + 17; // 跑步，随时可以开跑，但闪烁需要蓝量支持
        if (M >= 10) {
            // 有蓝就blink
            blink[i] = blink[i - 1] + 60;
            M -= 10;
        } else {
            // 没蓝就rest
            blink[i] = blink[i - 1];
            M += 4;
        }
        maxLen[i] = max(move[i], blink[i]); // 注意这并非局部最优解
        if (maxLen[i] >= S) {
            cout << "Yes" << endl << i << endl;
            return 0;
        }
    }
    cout << "No" << endl << maxLen[T] << endl;
    return 0;
}