解题报告 P1095 守望者的逃离【NOIP2007PJ】

题目内容

P1095

大意：要在 t 秒内逃离 s 距离，每秒可以选择跑步（17m/s），闪现（60m/s）且消耗 10 点蓝，回蓝（4 点一秒），求是否能逃离，若能，求最短时间，若不能，求最长距离

解题思路

这题设计状态比较麻烦，如果都要一起考虑的话明显不行，所以只能分跑步和闪现两种情况来考虑。

设 f_i 为第 i 秒能跑的最远距离。

先考虑闪现，如果蓝够的话，就拼命闪现，蓝不够就回蓝直到蓝够了为止，再考虑跑步，如果发现某一秒跑步能达到的距离比闪现更远的话，更新他。

这样的方法就将需要考虑蓝和不考虑蓝的情况分开了，减少了难度，具体代码：

#include <cstdio>

int M,S,T,f[300005];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d %d",&M,&S,&T);
    int maxs=0;
    for(int t=1;t<=T;t++)
    {
        if(M>=10)//蓝够
            f[t]=f[t-1]+60,M-=10;//闪现
        else
            f[t]=f[t-1],M+=4;//回蓝
    }
    for(int t=1;t<=T;t++)
    {
        f[t]=max(f[t],f[t-1]+17),maxs=max(maxs,f[t]);//如果跑步更优，更新
        if(f[t]>=S)
        {
            printf("Yes\n%d\n",t);
            return 0;
        }
    }
    printf("No\n%d\n",maxs);
    return 0;
}