wzy在跑步，由于昨天下雨了，所以跑道上某些位置堆积了雨水。wzy并不希望自己踩到水坑，所以当他将要踩到水坑时候他会选择跳过去。 具体的，跑道可以抽象为长度为n的序列，wzy从位置1出发，目的地是到达位置n。跑道上会有m个位置存在积水，他每次可以跳1到k单位长度正整数的距离，问wzy最少可以踩到几次水坑到达位置n。 输入描述 输入第一行三个正整数n，m，k，分别代表路径的长度，积水的个数以及wzy一次最远可以跨多远。 第二行共m个正整数ai，分别代表第i个水坑的位置。 输出描述 输出共一行，一个正整数，表示wzy至少踩到几次水坑才能到达位置n

这是一个典型的动态规划问题。我们可以分析出状态转移方程：

设 dp[i] 表示从起点到第 i 个位置最少踩到的水坑数目，则有：

dp[i] = min(dp[i - j]) + (a[i]=1)

其中 j 的取值范围为 [1, k]，a[i] 表示第 i 个位置是否有积水。

代码实现如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n + 1, 0);

    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        a[x] = 1;
    }

    vector<int> dp(n + 1, INF);
    dp[1] = 0;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= k && i - j >= 1; j++)
        {
            dp[i] = min(dp[i], dp[i - j] + a[i]);
        }
    }

    cout << dp[n] << endl;

    return 0;
}

时间复杂度为 O(nk)，可以通过本题。