今天久违的带来一题，P1095 [NOIP 2007 普及组] 守望者的逃离。这道题很有意思，是一道判断如何逃离更快的问题。直接贴一下我之前的复杂代码。

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long m,s,t;
    cin>>m>>s>>t;
    vector<long long> vec (t+1);
    for(int i=1;i<=t;i++){
        if(m>=10){
            vec[i]=vec[i-1]+60;
            m=m-10;
        }else{
            if(m>1&&(t-i)>=((10-m)/4)+1){
                m=m+4;
                vec[i]=vec[i-1];
            }else{if((vec[i-1]-s)>=120&&t-i>=6){
                 m=m+4;
                 vec[i]=vec[i-1];
            }else{
                vec[i]=vec[i-1]+17;
            }
            
        }
        }
    }
    if(vec[t]<s){
        cout<<"No"<<endl<<vec[t];
    }else{
        for(int i=1;i<=t;i++){
            if(vec[i]>=s){
                cout<<"Yes"<<endl<<i;
                break;
            }
                
        }
    }
    return 0;
}

我试图通过复杂的判断来寻找最优解，题目给的两个样例倒是通过了，最后的测试没有通过。那么先从我的错误开始，我是怎么想的呢，在这道题里闪烁的速度很快，那么自然是闪烁比直接走好，但是闪烁是有代价的，并不能一直闪烁，需要消耗魔力，如果魔力不足的时候就需要等待回复。经过计算，假如剩余魔力有2点及以上，3秒之内就可以闪烁，平均速度是比走快的。但如果魔力在2点以下，如果在120m以上，7秒可以闪烁两次，恢复总共用5秒，平均速度是17.14m/s，要比走快的。所以如果时间充分肯定是能闪烁就闪烁，但假如时间不够恢复而距离又很近，那么肯定是直接走走的距离长。按照这个思路，我完成了我的代码，但是结果并不对，我后来想到其实距离大于119就行，但改了这个还是错误的。

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long m, s, t;
    cin >> m >> s >> t;
    vector<long long> vec(t + 1, 0);
    
    for(long long i = 1; i <= t; i++){
        if(m >= 10){
            vec[i] = vec[i - 1] + 60;
            m -= 10;
        } else {
            // 判断是否值得等待恢复魔法
            long long need_wait = ceil((10.0 - m) / 4);
            
            if(need_wait <= (t - i) && (s - vec[i - 1]) > 119 && (t - i) >= 7) {
                // 处理连续恢复的情况 - 修复数组越界问题
                long long steps = min(7LL, t - i + 1); // 确保不超过数组边界
                
                for(long long j = 0; j < steps; j++) {
                    if(i + j > t) break;
                    
                    if(j == 3 || j == 6) { // 在第4和第7秒使用闪烁
                        if(m >= 10) {
                            vec[i + j] = vec[i + j - 1] + 60;
                            m -= 10;
                        } else {
                            vec[i + j] = vec[i + j - 1] + 17;
                        }
                    } else {
                        vec[i + j] = vec[i + j - 1];
                        m += 4;
                    }
                }
                i += steps - 1; // 跳过已处理的时间
            } else if(need_wait <= (t - i)) {
                // 单次恢复
                vec[i] = vec[i - 1];
                m += 4;
            } else {
                // 直接跑步
                vec[i] = vec[i - 1] + 17;
            }
        }
        
        if(vec[i] >= s) {
            cout << "Yes" << endl << i << endl;
            return 0;
        }
    }
    
    cout << "No" << endl << vec[t] << endl;
    return 0;
}

然后我让AI按照我的逻辑修正了一下，测试对的数量增加了，但还是有几个是错误的。由于不能看到详细的输入和输出是什么，我也不知道是什么情况没有考虑到。于是只能由此作罢，但可以看到这样正面做题，需要考虑的情况尤其多，极为复杂。那么让我们换一种思路，我们先就全部闪烁，然后再把每一步改成如果是走路会怎么样。详细请看接下来的代码。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int M, S, T;
    cin >> M >> S >> T;
    vector<int> dp(T + 1, 0);
    int m = M;
    
    // 第一阶段：优先使用闪烁法术
    for (int i = 1; i <= T; i++) {
        if (m >= 10) {
            dp[i] = dp[i - 1] + 60;
            m -= 10;
        } else {
            dp[i] = dp[i - 1];
            m += 4;
        }
    }
    
    // 第二阶段：考虑跑步的替代方案
    for (int i = 1; i <= T; i++) {
        dp[i] = max(dp[i], dp[i - 1] + 17);
        
        // 如果已经能够到达终点，立即输出
        if (dp[i] >= S) {
            cout << "Yes" << endl << i << endl;
            return 0;
        }
    }
    
    // 如果不能到达终点，输出最远距离
    cout << "No" << endl << dp[T] << endl;
    return 0;
}

可以看到代码也比较简单，这个代码是正确的。那么他为什么正确，又是什么角度来分析这个问题的。先是优先使用法术，没有就恢复。这样我们就得到了一个数组，那么在这个基础上，我们每一步改成假如是跑步会怎么样，假如那一步闪烁了，那么肯定闪烁要比走路距离大，但如果没闪烁，那么就是走路比恢复的时候大。这样子既可以避免已经可以到了，还要等恢复再闪烁，或是没有时间闪烁了，多走几步，让距离最大。这样子，假如距离到终点了，那么就是最短时间。如果到最后都没到，那么数组的最后就是最远距离。可以看到换这个角度解题，思路就比较清晰，代码量也少。