洛谷P1095 守望者的逃离题解

P1095 守望者的逃离

题目传送门-Luogu

30tps：

dfs搜索 每一秒内，可以选择跑 17m ，瞬移 60m（有足够的魔法值）或者是原地休息 时间复杂度：O(3^T)

核心代码：

void dfs(int x){
if(x>=t){
maxn=max(maxn,sum);
minn=min(minn,t);
return;
}
if(sum>=s){
maxn=max(maxn,sum);
minn=min(minn,x);
return;
}
// 选择跑17m
sum+=17;
dfs(x+1);
sum-=17;
// 选择使用魔法
if(m>=10){
m-=10;
sum+=60;
dfs(x+1);
m+=10;
sum-=60;
}
// 选择原地休息
m+=4;
dfs(x+1);
m-=4;
}

100pts

dp思路 计算出第 i 秒最多走多少米

确定dp数组及下标含义：

dp_i 表示第 i 秒最远能走到的距离

预处理：

思路：

如果有足够的魔法值，那就瞬移，否则原地休息

实现细节：

如果当前m>=10：

dp_i=dp_{i-1}+60

m=m-10

否则：

m=m+4

预处理代码：

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

动态转移方程：

转移跑步的情况

dp_i=max(dp_i,dp_{i-1}+17)

动态转移代码：

for(int i=1;i<=t;i++){
dp[i]=max(dp[i],dp[i-1]+17);
}

时间复杂度：O(T)

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[300010];
signed main(){
int m,s,t;
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++){
dp[i]=max(dp[i],dp[i-1]+17);
if(dp[i]>=s){
cout<<"Yes\\n"<<i;
return 0;
}
}
cout<<"No\\n"<<dp[t];
return 0;
}

AC记录