AcWing 431. 守望者的逃离
原题链接
简单
作者:
摆神
,
2024-04-24 17:53:38
,
所有人可见
,
阅读 1
守望者的逃离
状态表示:f[n] 表示前n秒最大移动距离
枚举出所有可能性:
状态计算:两个方面:1使用技能2徒步移动
1:1)积攒技能
2)使用技能
2:一秒17米
算法:线性DP
时间复杂度:O(n^2)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int m,s,t,T;
int f[300010];//每段时间下最长距离
int main(void)
{
cin >> m >> s >> t;
//先计算出只使用技能下每秒的移动距离
for(int i = 1;i <= t;i ++){
if(m >= 10){
m -= 10;
f[i] = f[i-1] + 60;
}
else{
m += 4;
f[i] = f[i - 1];
}
}
//抽插出徒步每秒的动的距离和使用技能下移动的最大距离
for(int i = 1;i <= t;i ++) f[i] = max(f[i-1] + 17 , f[i]);
//判断结果
int res = 0;
for(int i = 1;i <= t;i ++){
if(f[i] >= s){
cout << "Yes" << endl;
cout << i << endl;
break;
}
if(i == t) res = 1;
}
if(res == 1){
cout << "No" << endl;
cout << f[t] << endl;
}
return 0;
}