洛谷 P1095 NOIP2007普及组 守望者的逃离 题解【贪心】【DP】
点击量：1030
题目标签是 贪心+DP，但是实际上我是贪心+模拟出来结果的（不知道是不是数据弱了，欢迎dalao们hack）
题解中有关贪心的内容我都会把它加粗变大
定义一下
s是距离,$ v=s/t$是单位时间的速度，使用闪现的时候是$ v=60/1=60$，正常行走的时候是$ v=17/1=17$。积攒一个闪现加上释放：最好情况是魔法在10或以上，$ v=60/1=60$；最坏情况是没有魔法：积攒和释放共需要4秒，平均速度v就是$ v=60/4=15$。
首先，有魔法（=10）的时候，一定要用闪现，这时速度是最快的，v=60，这里是贪心的一个点，尽可能让速度快。
当魔法耗尽时（<10），有两种情况：
1.剩余0~1，补充3次魔法可以用闪现，平均速度是v=60/4=15，能走60m，耗费4秒，但比行走慢；补充5次魔法可以用两次闪现，平均速度是v=120/7=17.14，能走120m，耗费7秒，比行走快。
2.剩余2~9，补充1~2次魔法后可以用一次闪现，平均速度分别是$ v=60/2=30,v=60/3=20$，耗费2秒和3秒，都比行走快。
因此，在以上两种情况中，离终点较远的情况下，闪现是比行走要快的，同理是贪心的思想。
除此之外，我们还要特判快到终点（定为$s<68$）的情况，利用表格来说明
| 剩余魔法 | 0~1 | 2~5 | 6~9 |效果|
| 使用1次闪现 |耗时4s|耗时3s|耗时2s|距离60m|
| 不使用闪现 |耗时1s|耗时1s|耗时1s|距离17m||
列出下一次闪现需要几秒恢复：$ f(m)=(10-m-1)/4+2$（算上使用的1s）向下取整
所以f(0)=4,s=60而4s可以走（正常行走）68m
f(1)=4,4s可以走68m
因此在t>=4且s<68时正常行走就可以出去
f(2)=3,4s可以走51m
f(3)=3,f(4)=3,f(5)=3,f(6)=2,
f(7)=2,f(8)=2,f(9)=2
均同理
以上判断方程为(sum最终结果,m因为在while循环中耗尽,m<10)
$ if((9-m)/4+2>=((s-1)/17+1))$
if(m<10&&t>=(s-1)/17+1&&(9-m)/4+2>=((s-1)/17+1))
{
t-=(s-1)/17+1;
s=0;
break;
} $ (9-m)/4+2$ 是使用闪现所耗费的总时间
$ ((s-1)/17+1))$是行走耗费的总时间
行走耗时更少的话当然是选择行走了，因为可以拆成更少的时间段来进行，举个栗子
| 剩余魔法 | Δm |1|
| 剩余距离 | Δs |18|
| 剩余时间 | Δt |3|
可以看出，当Δs=1$时，只需2s就可以直接走出去了，而补充魔法用闪现需要$4s$
这里当然是选择贪2s了，这些思想在代码里都有体现。
Code：
#include<cstdio>
int main()
{
int m,s,t,S,T;
scanf("%d%d%d",&m,&s,&t);
S=s;//S,T用来存初始值，方便最后一步算出结果
T=t;
while(s>0&&t>0)//循环的边界，也是最终判断的依据
{
if(m>=10)//当m>=10时，用闪现是最快的，没有之一，贪心思想
{
m-=10;
s-=60;
t--;
}
else if(m<10&&((9-m)/4+1)<t)//判断是休息还是直接开溜
{
if((9-m)/4+2>=((s-1)/17+1))//当能直接开溜的时候，贪心贪最小的
{
t-=(s-1)/17+1;
s=0;
break;
}
m+=4;
t--;
}
else//不特判的情况，也不休息，直接正常行走，比如当t较小的时候
{
s-=17;
t--;
}
}
if(s<=0)
printf("Yes\n%d\n",T-t);
else if(t<=0)
printf("No\n%d\n",S-s);
return 0;
}
说点什么