线性dp
f[i] 表示第i秒时最多能跑多少米,那么如何维护f[i],
我们发现在能闪烁的情况下闪烁的结果一定优于跑步,那么我们可以先用闪烁来更新f[i]
再用 插入 的方法把跑步加到到f数组中
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3e5 + 10, V = 17;
int t, m, f[N], s;//f[N]表示在第i秒时可以跑到的最大距离
int main()
{
cin >> m >> s >> t;
for(int i = 1; i <= t; i ++)
{
if(m >= 10)
{
f[i] = max(f[i], f[i - 1] + 60);
m -= 10;
}
else m += 4, f[i] = f[i - 1];
}
for(int i = 1; i <= t; i ++) f[i] = max(f[i], f[i - 1] + 17);
int is_success = false;
int tag = t;
for(int i = 1; i <= t; i ++)
if(f[i] >= s)
{
is_success = true;
tag = i;
break;
}
if(is_success)
{
puts("Yes");
cout << tag << endl;
}
else
{
puts("No");
cout << f[t] << endl;
}
return 0;
}