1108守望者的逃离(dp动态规划）

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

long long M;//魔法初值

long long S;//出口距离

long long T;//沉没时间

long long dp[500005];//存每一秒的最优解，这里开大一点，题目没明确说。

int main()

{

cin >> M >> S >> T;

//下面的思路就是，我们先将魔法值用完，之后等它恢复，有十点了我们就闪现一次

//这时得到的 dp[]数组中有很多相同的值，因为我们在恢复魔力时，是不能动的。

for (int i = 1; i <= T; i++)

{

if (M >= 10)

{

dp[i] = dp[i - 1] + 60;

M -= 10;

}

else

{

dp[i] = dp[i - 1];

M += 4;

}

}

//下面我们就只走，这时我们肯定会替换掉上面 dp[]数组中的一些值，替换的过程就是寻找最优解的过程

//也就在这时，我们就比较了这个时间段，是停下来闪现好，还是直接跑比较好

//同时，我们也记录了在 T 时间里，我们跑过的最远距离 dp[T]

//而 i 的值又恰好是我们经过的时间

//根据题目要求

//成功的话输出 "Yes"和所用的最短时间 i

//失败的话输出 "N0" 和跑过的最远距离 dp[T]

//注意大小写,我交了好几次，就是因为"Yes"没写对出错了

for (int i = 1; i <= T; i++)

{

dp[i] = max(dp[i], dp[i - 1] + 17);

}

for(int i=1;i<=T;i++)

{

if (dp[i] >=S)

{

cout << "Yes" << endl;

cout << i << endl;

return 0;

}

}

cout << "No" << endl;

cout << dp[T] << endl;

return 0;

}