题目内容

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;
}
最后修改日期:2020年3月9日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。