[luogu] P1095 [NOIP2007 普及组] 守望者的逃离 线性DP

• • • 前言
    • 思路
    • CODE

传送门 : https://www.luogu.com.cn/problem/P1095
分状态 , 找数组 , 进行转移

一开始 直接分了一个 (有蓝|无蓝) 的状态 但是这样子就没法维护另一个状态了

其实不管什么都是随着秒数变的

因此我们状态分析可以

• 当前时刻
  1. 走 2.停 3.闪

因此我们的状态数组就可以变成 F[i] 表示当前时刻走的位置

我们可以先处理闪现和回蓝的关系

然后我们在处理是否要走

于是就简单了

#include 
using namespace std;
using ll = long long;
const int N  = 3e5+10;

int f[N]; ///当前时刻 跑在了多少的位置
int m,s,t;
void solve()
{
    cin>>m>>s>>t;

    f[0] = 0 ;

    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]=s)
        {
            cout<<"Yes"<