题解 P1095 【守望者的逃离】

lili_flyingcutter · 2017-08-05 16:47:08 · 题解

根据题意，守望者要在最短时间走最多的路程，而每秒有三种决策

我们不妨将跑步和使用闪烁法术分开处理

上代码

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[300001];
int main(){
    int m,s,t;
    scanf("%d%d%d",&m,&s,&t);
    for(int i=1;i<=t;i++){//处理闪烁法术
        if(m>=10)dp[i]=dp[i-1]+60,m-=10;//如果能用，就用
        else dp[i]=dp[i-1],m+=4;//否则休息
    }
    for(int i=1;i<=t;i++){dp[i]=max(dp[i],dp[i-1]+17);//处理跑步，dp[i]为使用法术和跑步的最大值（最优）
    if(dp[i]>=s){printf("Yes\n%d",i);return 0;}//如果超过了距离s，就成功了，输出yes
    }printf("No\n%d",dp[t]);//没成功，输出no
    return 0;
}