P1095 守望者的逃离

题意

一个守望者要逃离岛屿，他与岛屿的出口有S米的距离，有T秒的时间可以用来逃离，他有两种方式逃离：

1.每秒17m 2.用10点的魔力在一秒内走60米，其中，站在原地不动1s可以获得四点魔力，他的初始魔力为M

思路

每次能闪肯定要闪啊，于是，我们可以考虑在什么情况下，闪比直接跑要优。

首先我们肯定是要将能用的魔力值都用掉，接下是这样考虑的:

我们设k为我们当前过去了k天，m为我们当前尽剩m的魔力值

1.如果有m>=6，显然站一天再闪一天比跑两天要优，所以当k==2时就能闪了

2.如果有m>=2, 显然站两天再闪一天比跑三天要优，所以当k==3时就能闪了

3.如果有m>=0，显然站五天再闪两天比跑七天要优，所以当k==7时就能一次闪完了

代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int dp[30005],f[300005];
 4 int main(){
 5     int t,m,s,i,j,cnt,tim;
 6     scanf("%d%d%d",&m,&s,&t);
 7     tim=0;
 8     while(m>=10&&tim<t&&dp[tim]<s){
 9         tim++;
10         dp[tim]=dp[tim-1]+60;
11         m-=10;
12     }cnt=0;
13     if(dp[tim]>s){
14         printf("Yes
%d",tim);
15         return 0;
16     }
17     for(i=tim+1;i<=t;i++){
18         dp[i]=max(dp[i],dp[i-1]+17);
19         cnt++;
20         if(cnt==2&&m>=6){
21             dp[i]=dp[i-2]+60;
22             m-=6;
23             cnt=0;
24         }
25         if(cnt==3&&m>=2){
26             dp[i]=dp[i-3]+60;
27             m-=2;cnt=0;
28         }
29         if(cnt==7){
30             dp[i]=dp[i-7]+120;
31             cnt=0;
32         }
33         if(dp[i]>s){
34             printf("Yes
%d",i);
35             return 0;
36         }
37     }
38     printf("No
%d",dp[t]);
39     return 0;
40 }