P1095 [NOIP2007 普及组] 守望者的逃离题解

· · 题解

本蒟蒻的第一篇题解

思路：

  1. 定义一个 dp[i] ，表示第 i 秒最多能走都远。

  2. 先全部用闪烁，记录最远能走多远，因为闪烁平均每 3 秒能完成一次闪烁，能前进 60 米，而步行 3 秒只能前进 51 米，所以尽量选择闪烁。

  3. 由于可能会出现以下情况，我们要比较步行和闪烁哪个先到终点。

s=94
60        60          60
闪烁      恢复        恢复
dp[i]     dp[i+1]     dp[i+2]
闪烁      步行        步行
60        77          94
                      /\
                    / || \
                      ||
                     终点

这样就能完美 AC 了！

代码：

#include<bits/stdc++.h>//万能头文件
#define ll long long
using namespace std;
int m,s,t,ans,dp[10000010];
int main(){
    cin>>m>>s>>t;
    for(int i=1;i<=t;i++){//全部闪烁
        if(m>=10) dp[i]=dp[i-1]+60,m-=10;
        else m+=4,dp[i]=dp[i-1];
    }
    for(int i=1;i<=t;i++){
        if(dp[i]<dp[i-1]+17) dp[i]=dp[i-1]+17;//比较那个快
        if(dp[i]>=s){//到终点了就输出
            cout<<"Yes"<<endl<<i;
            return 0;
        }
    }
    cout<<"No"<<endl<<dp[t];//到不了终点
    return 0;
}