算法
(DP,线性DP) $O(T)$
首先比较跑步和放技能哪个更快:
- 跑步:平均一秒 $17$ 米
- 放技能:平均2.5秒恢复10点魔法,再加一秒闪烁时间,一共是3.5秒可以移动60米, 所以平均每秒 $17\frac{1}{7}$米
所以放技能稍快一些。
因此当我们有充足的放技能时间时,一定要放技能,所以只有最后一小段没时间放技能的时候,才会用跑步的方式。
然后考虑如何求解:
用f[i]
表示用i
的时间,最多可以跑多远。
先求出只用闪烁技能时,每秒最多可以跑多远。
再用跑步的方式来“插缝”,递推出结合两种方式时,每秒最多可以跑多远。
时间复杂度
状态总共有 $t$ 个,计算每个状态需要 $O(1)$ 的时间,所以总时间复杂度是 $O(t)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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)
{
printf("Yes\n%d\n", i);
success = true;
break;
}
if (!success) printf("No\n%d\n", f[t]);
return 0;
}
orz orz orz
orz
y总我老是学不会dp怎么办啊QAQ 有什么好的方法吗??
老是无法确定 f 数组要用多少维, 每一维代表什么
一维能解决不用二维,二维能解决不用三维。而且,DP很多情况下是靠经验。
y总太强了!!!
orz