题解：P13517 [KOI 2025 #2] 障碍物

### 一、递推及转移方程
>读题之后，考虑使用类似 递推 的方法，设 $f_i$ 表示走到 $i$ 坐标所需的最少移动次数。所以就可以得出没有障碍物的转移方程：
>$$
>f_{i+1} = f_{i-1} + 1
>$$
>这个转移方程的原因是：从一个点到另外一个点用跳两步的移动方法一定比走一步的移动方法要更优。
### 二、特殊情况：
>1. 两个障碍物紧挨在一起，也就是 $ x_i == x_{i-1}+1 $ 的时候，无论是跳还是走，都会到达有障碍物的地方，所以这时无法跳过所有障碍物，直接输出 `-1`。
>2. $i-1$、$i$ 或 $i+1$ 为障碍物。我们可以将障碍物的地方 $f_{x_i}$ 打上标记 $-1$，当跳两步的起点 $f_{i-1}$ 为 $-1$ 时，就只能从 $f_{i}$ 走一步的方法转移，也就是 $f_{i+1} = f_{i} + 1$；当走一步的起点 $f_{i}$ 为 $-1$ 时，就还是最初的方程。当$f_{i-1},f_{i}$都为  $-1$ ，或者 $f_{i+1}$ 本来就是 $-1$ 时，方程无法转移，$f_{i+1}$ 就只能是为 $-1$。
>::::::warning[注意]{open}
>$x_0$ 也设为 $-1$，但 $f_0$ 为 $0$。  
>:::::warning[为什么？]{open}
>因为当 $x_1 = 1$ 时，如果 $x_0$ 默认为 $0$ 的话，就会使 $ x_i == x_{i-1}+1 $ 成立，输出 `-1`，因此，上述这样保证了所有障碍物不会判多。
>:::::
>::::::

### 三、初始化、起止值和答案。
>因为转移方程最小下标为 $i-1$，且开始在下标 $0$，所以从 $1$ 开始。初始化 $f_0 = 0$。但因为我们没有考虑 $f_1$ 可能是从 $f_0$ 转移的情况，所以当 $f_1$ 不为 $-1$ 时，$f_1 = f_0+1$。最后终点为最后一个障碍物后面 $x_{n}+1$，所以循环起止点应为 $[1,x_{n}+1)$，答案为 $f_{x_{n}+1}$。  
### 四、标程：
```cpp
#include<bits/stdc++.h>

using namespace std;

int n,x[250005],f[250005];

int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d",&n);
    x[0] = -1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
        f[x[i]] = -1;
        if(x[i] == x[i-1]+1)
        {
            printf("-1");
            return 0;
        }
    }
    f[0] = 0;
    if(!(f[1] == -1))
    {
        f[1] = f[0]+1;
    }
    for(int i=1;i<x[n]+1;i++)
    {
        if((f[i] == -1 && f[i-1] == -1)|| f[i+1] == -1)
        {
            f[i+1] = -1;
        }
        else if(f[i] == -1)
        {
            f[i+1] = f[i-1]+1;
        }
        else if(f[i-1] == -1)
        {
            f[i+1] = f[i]+1;
        }
        else
        {
            f[i+1] = f[i-1]+1;
        }
    }
    printf("%d",f[x[n]+1]);

return 0;
}

```

正在渲染内容...