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

前言

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

思路

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

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

因此我们状态分析可以

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

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

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

然后我们在处理是否要走

于是就简单了

CODE

/**
- 跑 走 停
 ///每次消耗 10点 守望者的魔法速度为 4点每秒
**/
#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=10)
        {
            f[i]=f[i-1]+60;
            m-=10;
        }
        else
        {
            f[i]=f[i-1];
            m+=4;
        }
    }
    for(int i=1;i