CSP历年复赛题-P1095 [NOIP2007 普及组] 守望者的逃离

原题链接：https://www.luogu.com.cn/problem/P1095

题意解读：在有限的时间内，通过跑步或者闪烁两种方式，能跑出的最远距离是多少，以及是否能跑出出口。

解题思路：

1、贪心法

每一秒钟，都有两种选择：跑步（17米）、闪烁（60米，前提是蓝够10点，否则等待1s恢复4点蓝）

经过计算，恢复足够的蓝到闪烁需要3.5s，而3.5s跑步可以跑出59.5

因此，在时间充分的情况下，闪烁以及等待回蓝是最佳方案，但是在最后的几秒，跑步才是更佳！

所以，可以枚举每一秒，跑步、闪烁两种方式同步进行，计算各自前进的距离，下一秒跑步的距离要以之前两种方案跑出最远的距离为基准（闪烁跑得远就用闪烁，否则就跑步）

100分代码：

#include <bits/stdc++.h>
using namespace std;

int m, s, t;
int dist1; //跑步的距离
int dist2; //闪烁的距离

int main()
{
    cin >> m >> s >> t;
    for(int i = 1; i <= t; i++)
    {
        dist1 += 17; //跑步方式
        if(m >= 10) //闪烁方式
        { 
            dist2 += 60;
            m -= 10;
        }
        else
        {
            m += 4;
        }
        dist1 = max(dist1, dist2); //如果这一秒闪烁更远，跑步方式就改成闪烁

        if(dist1 >= s)
        {
            cout << "Yes\n" << i;
            return 0;
        } 
    }
    cout << "No\n" << dist1;
    return 0;
}

2、动态规划

状态表示：f[i]表示经过i秒能跑出的最大距离

状态转移：

  如果是闪烁：

    蓝够：f[i] = f[i-1] + 60，蓝减10

    蓝不够：f[i] = f[i-1]，蓝加4

  如果是跑步：

    f[i] = f[i - 1] + 17

可以第一轮枚举时间使用闪烁跑一遍，再枚举一遍时间用跑步补充，比较两者谁更有

  f[i] = max(f[i]，f[i-1] + 17)

初始化：f[0] = 0

结果：第一个f[i] > s，如果没有最远距离就是f[t]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 300005;
int m, s, t;
int f[N]; //f[i]为前i秒最多跑出的距离

int main()
{
    cin >> 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++)
    {
        f[i] = max(f[i], f[i-1] + 17);
    }
    for(int i = 1; i <= t; i++)
    {
        if(f[i] >= s)
        {
            cout << "Yes\n" << i;
            return 0;
        }
    }
    cout << "No\n" << f[t];
    return 0;
}