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

~~本蒟蒻的第一篇题解~~

思路：

定义一个 $dp[i]$ ，表示第 $i$ 秒最多能走都远。
先全部用闪烁，记录最远能走多远，因为闪烁平均每 3 秒能完成一次闪烁，能前进 60 米，而步行 3 秒只能前进 51 米，所以尽量选择闪烁。
由于可能会出现以下情况，我们要比较步行和闪烁哪个先到终点。

CPP

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

这样就能完美

AC

了！

代码：

CPP

#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;
}

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

文章操作

思路：

代码：

相关推荐

评论

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