P1095 [NOIP2007 普及组] 守望者的逃离

[NOIP2007 普及组] 守望者的逃离 - 洛谷

首先DP的套路就是先找状态

这题也找不出其他的状态了，只有时间一个

所以用f[i]表示时刻i能走多远

而仔细一想实际上决策只有跑、闪现、停三种决策

然而闪现的耗蓝要和跑步一同计算十分麻烦

于是把它们分开算：

先算闪现的，有以下框架

for i in range(1,t)

如果蓝量够

闪现，耗蓝

如果不够

停下，回蓝

接下来算走路，其实走路的只要维护之前算出的即可

因为之前已经算了只用闪现走多远，那么只要判断如果这一秒不闪或者不停（因为跑步不耗蓝）是否比之前更优即可

框架 for i in range(1,t)

如果这一秒走路比只闪现更优

那就走路，用走路替代闪现或停

同时，如果f[i]已经大于等于s，即逃出去了，那么输出并退出程序

转移方程：其实这题没什么转移方程，它不是传统DP所以没有传统的转移方程，只能说有点像基于时间轴的DP

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int m,s,t;
int f[N];
int sum;
int main()
{scanf("%d %d %d",&m,&s,&t);for(int i=1;i<=t;i++){if(m>=10){f[i]=f[i-1]+60;m-=10;}else{f[i]=f[i-1];m+=4;}}for(int i=1;i<=t;i++){if(f[i]<f[i-1]+17)f[i]=f[i-1]+17;if(f[i]>=s){printf("Yes\n");printf("%d\n",i);return 0;}}printf("No\n");printf("%d\n",f[t]);return 0;
}