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

设f[i]表示第i秒能到达最远距离

显然一直闪现再回魔再闪现更优。。但是最后几秒可能因为回魔时间不够而要选择跑路能在最后几秒达到最远距离，所以两遍DP？（我也不知道是不是DP），实际上最优值数组只有最后几秒变化，算两次dp。

这题有三种决策，跑路，回蓝，闪现。我们可以把它操作一分为二，互不影响

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T> 
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T> 
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('
');
}
const int N=3e5+79;
int m,s,t;
int f[N];
int main() {
    read(m);read(s);read(t);
    memset(f,0xff,sizeof f);
    f[0]=0;
    rep(i,1,t){
    	if(m>=10){
    		f[i]=f[i-1]+60;
    		m-=10;
		}else{
			m+=4;
		    f[i]=f[i-1];
		}
	}
	rep(i,1,t){
		if(f[i]<f[i-1]+17) f[i]=f[i-1]+17;
		if(f[i]>=s){
			puts("Yes");
			out(i);
			return 0;
		}
	}
	puts("No");
	out(f[t]);
	return 0;
}