P1095 [NOIP 2007 普及组] 守望者的逃离
洛谷地址：https://www.luogu.com.cn/problem/P1095
题目背景
NOIP2007 普及组 T3
题目描述
恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。
守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。
为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。
守望者的跑步速度为 17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 1s 内移动 60m，不过每次使用闪烁法术都会消耗魔法值 10 点。守望者的魔法值恢复的速度为 4 点每秒，只有处在原地休息状态时才能恢复。
现在已知守望者的魔法初值 M，他所在的初始位置与岛的出口之间的距离 S，岛沉没的时间 T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。
注意：守望者跑步、闪烁或休息活动均以秒为单位，且每次活动的持续时间为整数秒。距离的单位为米。
输入格式
输入数据共一行三个非负整数，分别表示 M，S，T。
输出格式
输出数据共两行。
第一行一个字符串 Yes 或 No，即守望者是否能逃离荒岛。
第二行包含一个整数。第一行为 Yes 时表示守望者逃离荒岛的最短时间；第一行为 No 时表示守望者能走的最远距离。
输入输出样例
输入输出样例
输入 #1复制
39 200 4
输出 #1复制
No
197
输入 #2复制
36 255 10
输出 #2复制
Yes
6
说明/提示
对于 30% 的数据，1≤T≤10，1≤S≤100；
对于 50% 的数据，1≤T≤10
3
，1≤S≤10
4
；
对于 100% 的数据，1≤T≤3×10
5
，0≤M≤10
3
，1≤S≤10
8
。
题意解读：在有限的时间内，通过跑步或者闪烁两种方式，能跑出的最远距离是多少，以及是否能跑出出口。
解题思路：
1、贪心法
每一秒钟，都有两种选择：跑步（17米）、闪烁（60米，前提是蓝够10点，否则等待1s恢复4点蓝）
经过计算，恢复足够的蓝到闪烁需要3.5s，而3.5s跑步可以跑出59.5
因此，在时间充分的情况下，闪烁以及等待回蓝是最佳方案，但是在最后的几秒，跑步才是更佳！
所以，可以枚举每一秒，跑步、闪烁两种方式同步进行，计算各自前进的距离，下一秒跑步的距离要以之前两种方案跑出最远的距离为基准（闪烁跑得远就用闪烁，否则就跑步）
100分代码：
#include <bits/stdc++.h>
using namespace std;
int m, s, t;
int dist1; //跑步的距离
int dist2; //闪烁的距离
int main()
{
cin >> m >> s >> t;
for(int i = 1; i <= t; i++)
{
dist1 += 17; //跑步方式
if(m >= 10) //闪烁方式
{
dist2 += 60;
m -= 10;
}
else
{
m += 4;
}
dist1 = max(dist1, dist2); //如果这一秒闪烁更远，跑步方式就改成闪烁
if(dist1 >= s)
{
cout << "Yes\n" << i;
return 0;
}
}
cout << "No\n" << dist1;
return 0;
}
2、动态规划
状态表示：f[i]表示经过i秒能跑出的最大距离
状态转移：
如果是闪烁：
蓝够：f[i] = f[i-1] + 60，蓝减10
蓝不够：f[i] = f[i-1]，蓝加4
如果是跑步：
f[i] = f[i - 1] + 17
可以第一轮枚举时间使用闪烁跑一遍，再枚举一遍时间用跑步补充，比较两者谁更远
f[i] = max(f[i]，f[i-1] + 17)
初始化：f[0] = 0
结果：第一个f[i] > s，如果没有最远距离就是f[t]
100分代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int m, s, t;
int f[N]; //f[i]为前i秒最多跑出的距离
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);
}
for(int i = 1; i <= t; i++)
{
if(f[i] >= s)
{
cout << "Yes\n" << i;
return 0;
}
}
cout << "No\n" << f[t];
return 0;
}
纯贪心题，可以模拟每一秒的状态。换一种思路：假设有守望者会分裂！分裂出来的那个只会用魔法（用不了就休息），正版守望者只会跑步，如果盗版超过了正版，就把正版的路程赋值为盗版的路程（贪心基本原则：能用就用，用不了就跑或休息），详细见程序注释。
#include<cstdio>
using namespace std;
int m,s,t,r1,r2,t1;
int main()
{
scanf("%d%d%d",&m,&s,&t);
while (r1<s)
{
++t1;//时间
if (t1>t)//没时间了！！
{
printf("No\n%d",r1);
return 0;
}
if (m>=10)//能用就用
{
m-=10;
r2+=60;//盗版的路程
}
else m+=4;//原地休息
r1+=17;//正版跑步
if (r2>r1) r1=r2;
}
printf("Yes\n%d",t1);
return 0;
}