守望者的逃离 （C++代码）

解题思路:

根据题意，守望者要在最短时间走最多的路程，而每秒有三种方法：休息（魔法恢复4），跑步（移动十七米），闪烁法术（花费10魔法，移动60米）。可以得到如下信息：
1.休息和闪烁魔法是有关联的（要不然还不如不休息）。
2.有魔法的情况下，尽量使用闪烁魔法（因为闪烁法术移动最远）。
3.在魔法不够的情况下，对休息（等待魔法恢复使用闪烁法术）还是跑步进行选择。
   为了理清信息，不妨将跑步和使用闪烁法术分开处理。
   设想：
   1.如果守望者不会跑步，即第i秒的能到达最大距离为f[i],则：
       f[i]={f[i-1]+60 当m（魔法）>=10时，同时m=m-10
             f[i-1]    当m<10时，同时m=m+4
       通过这样一个预处理，解决了闪烁法术的使用。
   2.把跑步的情况加入，则：
     f[i]=MAX(f[i],f[i-1]+17)  (注意：令f[0]=0）
       如此,得到了解决问题的递推式.当ft<S时，输出“No”及f[t]值，否则，就输出“Yes”及最快的离岛时间i。
       综合上述分析，具体实现步骤如下：
       1.读入数据M，S，T。
       2.计算只使用闪烁法术时的每秒最大距离。
       3.计算加入只使用跑步时的每秒最大距离，如果在某时刻刚好离岛，则输出离岛时间，结束。
       4.如果没有离岛，输出最远距离，结束。

注意事项:

参考代码:

#include<iostream>
 using namespace std;
 long long m,s,t,i,f[500005]; 
 int main()
 {
    cin>>m>>s>>t;
    for(i=1;i<=t;i++)//循环时间 
        {
            if(m>9)
            {
                f[i]=f[i-1]+60;
                m-=10;      //闪现 
            } 
            else
            {
                f[i]=f[i-1];
                m+=4;       //回蓝 
            }
        }
    for(i=1;i<=t;i++)
    {
        if(f[i]<f[i-1]+17) f[i]=f[i-1]+17;//判断跑步
        if(f[i]>=s)

        {
            cout<<"Yes"<<endl;
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl<<f[t]<<endl;
    return 0;
 }

2018-10-1308:47:11