AcWing 431. 守望者的逃离
原题链接
简单
作者:
HiCode_001
,
2019-11-06 01:40:02
,
所有人可见
,
阅读 655
题意分析:
1)通过分析计算,2.5s可以恢复10点魔法,使用魔法闪现花费1s,所以3.5秒可以移动60米,可以计算出平均速度为17*1/7米/秒
2)需要在规定时间内是否可以成功到达,不到达最大奔跑距离为多少
考察知识点:
DP,线性DP
时间复杂度:O(t) t种状态
思路分析:
1)结合题意分析1可知,我们需要尽量多的使用魔法
2)考虑问题求解:
a.使用f[i]表示花费i时间后奔跑的距离
b.先求出只是用技能闪烁时,最多可以跑多远
c.剩下的就用奔跑来填补
d.结合两种方式,求出最大可以奔跑的距离和s比较求出解
#include <iostream>
using namespace std;
const int N = 300010;
int m,s,t;
int f[N];
int main(){
cin >> m >> s >> t;
for(int i = 1; i<=t ; i++){
if(m>=10){
f[i] = f[i-1]+60;
m -=10;
}else{
f[i] = f[i-1];
m +=4;
}
}
for(int i = 1; i<=t; i++) f[i] = max(f[i],f[i-1]+17);
bool success = false;
for(int i = 1; i<=t; i++){
if(f[i]>=s){
cout << "Yes" <<endl;
cout << i;
success = true;
break;
}
}
if(!success) cout << "No" << endl << f[t];
return 0;
}