luogu p1095 守望者的逃离

守望者的逃离

标签:贪心 dp

事实证明DP思维难度不因为普及组而变简单

这题看完之后脑子就会有两种想法，一种都没有就算了

第一个想法是贪心

但是很明显各种条件和边界很难处理QAQ，所以emm我放弃了

第二个想法是动规

动规的状态很好想

\(f[i][j]\)代表时刻\(i\)的时候魔法值为\(j\)的最远距离

转移方程
\[ \large f[i][j] =max \begin {cases} f[i-1][j-4]\f[i-1][j] +17\f[i-1][j+10]+60 \end {cases} \]
然而看了数据范围
\[ 1\le T \le 300000 \quad 0 \le M \le 1000 \]
算了一下这玩意内存爆炸

自闭了一会看了题解分析：分开求解跑路和传送……

我们先不说怎么能想到，其实是我想不到，我们先说为什么这样做对

分析

我们可以理解成每次类似贪心地尝试各种方案

先跑跑只采用传送的方法，传送完之后我们开始尝试在跑一遍跑路方案。

也就是分成两个状态,定义\(f[i]\)表示在\(i\)时刻的位置
\[ \large telepoint：f[i]=\begin{cases} f[i-1] + 60,M-10(M\ge10)\f[i-1],M+4(M<10) \end{cases} \\large run:f[i]=max\begin{cases} f[i-1]+17\f[i] \end{cases} \]
我们在某一秒假如放弃恢复选择跑路，假如能跑出去，当然是好的。

假如不能呢？那也不会改变我们的\(f\)的值，因为我们很容易发现，贪心地来说只要能传送，它永远是远优于跑步的。

假如说我们魔力不够必须停下来补魔恢复，那么我们可以尝试放弃补魔恢复，改成跑几步试试，因为恢复加传送最坏只需要4s,平均下来是15m/s,，略逊于跑步，但这是个保守的估计，更多的的时候传送更优。

假如跑步更优的情况出现了，我们就可以认为补魔恢复的那段时间，我们换成跑路了，只会让结果更优更符合答案。但假如跑路不够优呢？那其实不会影响传送的更优解，我们依然可以把跑路的那几秒看作在补魔恢复。

这种局部尝试替换寻求最优解的思维是很值得学习的

代码

//by Saber Alter Official
//Erishikigal & Ishtar
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>

typedef long long ll;
typedef unsigned long long ull;

const int N = 300015;

int M, S, T;

int mov[N];
bool reach;

void DP() {
    for(int i = 1;i <= T;i++) {
        /*use telepoint*/
        if(M >= 10) {
            mov[i] = mov[i - 1] + 60;
            M -= 10;
        }
        else {
            mov[i] = mov[i - 1];
            M += 4; 
        }
    }
    
    for(int i = 1;i <= T;i++) {
        mov[i] = std::max(mov[i], mov[i - 1] + 17);
        
        if(mov[i] >= S) {
            reach = true;
            printf("Yes\n%d", i);
            return ;
        }
    }
    
    if(!reach) {
        printf("No\n%d", mov[T]);
    }
}

int main() {
    scanf("%d %d %d", &M, &S, &T);
    
    DP();
    
    return 0;
}

luogu p1095 守望者的逃离

原文：https://www.cnblogs.com/Fructose-Ryllis/p/11837341.html