P1095 守望者的逃离
斯德哥尔摩
2018-10-21 09:56:19
[P1095 守望者的逃离](https://www.luogu.org/problemnew/show/P1095)
## 要用膜法打败膜法！
首先，两种情况很烦人。。。
我们不妨举几个小栗子：
1. 膜法：假设最初的膜法值为$0$，则有：
$$t_1=0,t_2=0,t_3=0,t_4=60$$
即：前三秒恢复膜法值，第四秒闪现。
2. 跑路：不使用闪现，则有：
$$t_1=17,t_2=34,t_3=51,t_4=68$$
即：一直跑路。
不难发现当有膜法值时，先把膜法值用到$0$为止，不够则恢复，够则闪现。
然后在这个基础上，用一直跑路和闪现取最大值。
最后判断一下就好。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 300010
using namespace std;
int m,s,t,dp[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
m=read();s=read();t=read();
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);
if(dp[i]>=s){//有解
printf("Yes\n%d\n",i);
return;
}
}
printf("No\n%d\n",dp[t]);//无解
}
int main(){
work();
return 0;
}
```