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;
}