Title:
P1809 wzy’s running

Description:
wzy is running. Because it rained yesterday, rainwater accumulated in some places on the track. wzy doesn’t want to step into a puddle, so when he is about to step into a puddle, he will choose to go there. Specifically, the runway can be abstracted as a sequence of length nine. wzy starts from position 1 and the destination is the arrival position. There will be m positions on the runway with water accumulation. He can move one unit length at a time. wzy can step on puddles at least a few times to reach position nine.

Input Description:
Enter three positive integers n, m, and k in the first line. n represents the length of the path, m represents the number of accumulated water positions, and k represents the maximum distance wzy can span at one time. The second line contains m positive integers, representing the positions of the puddles.

Output Description:
Output a single positive integer, indicating the minimum number of times wzy has to step on puddles to reach position nine.

Sample Input:
6 3 2
2 3 5

Sample Output:
1

Sample Explanation:
There are puddles at positions 2, 3, and 5. wzy is initially at position 1, and he can only reach positions 2 and 3. A possible path is 1 – 2 – 4-6, with a total of 1 puddle. Obviously, this is one of the ways to step into the fewest puddles.

Constraints:

• n < 10000
• m < n
• k < 50

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int get_min(vector<int>& dp, int k, int start, int n) {
    int min_x = dp[start];
    for (int i = start; i < min(start + k, n + 1); i++) {
        if (dp[i] < min_x) {
            min_x = dp[i];
        }
    }
    return min_x;
}

int main() {
    int n, m, k, x;
    cin >> n >> m >> k;
    vector<int> v(n + 1, 0); // Use vector instead of array, and initialize to 0
    for (int i = 1; i <= m; i++) {
        cin >> x;
        v[x] = 1;
    }
    vector<int> dp(n + 1); // Use vector instead of array
    dp[1] = 0;
    for (int j = 2; j <= n; j++) { // Modify the loop's starting position to 2
        if (v[j] == 0) {
            dp[j] = get_min(dp, k, max(j - k, 1), j - 1); // If the current position is not a puddle, consider the maximum jump distance k
        }
        else {
            dp[j] = get_min(dp, k, max(j - k, 1), j - 1) + 1; // If the current position is a puddle, consider the maximum jump distance k
        }
    }
    cout << dp[n] << endl;

    return 0;
}

I believe my algorithm is correct, yet I’m receiving a Wrong Answer (WA) upon submission. Therefore, I would like to seek advice on whether the issue lies with the algorithm itself or if there are other aspects that need consideration.