题解 | #[NOIP2007]守望者的逃离#

$dpdp$做法，先全用魔法更新一遍动态数组，然后再加入常规走法更新
AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int dp[N];
int main(void)
{
	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
		{
			dp[i] = dp[i - 1];
			m += 4;
		}
	}
	for (int i = 1; i <= t; i++)
	{
		dp[i] = max(dp[i], dp[i - 1] + 17);
		if (dp[i] >= s)
		{
			cout << "Yes" << endl;
			cout << i << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	cout << dp[t] << endl;
	return 0;
}

还有一种做法，但是比较麻烦，分析出用一次魔法可以走$6060$米，只有等$1,21,2$次回复魔法，平均速度可以超过$1717$米每秒。还有一种使用魔法划算的方法是等$55$次，用两次魔法，这样可以走120米，平均速度刚好比$1717$米每秒快一点。其他位置全部使用普通走法即可。
注：比较麻烦，代码很长