A21777 过河 全站首发题解

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

void solve() {
    int l;
    std::cin >> l;
    int s, t, m;
    std::cin >> s >> t >> m;

    std::vector<int> stones(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> stones[i];
    }
    std::sort(stones.begin(), stones.end());

    if (s == t) {
        int count = 0;
        for (int stone_pos : stones) {
            if (stone_pos % s == 0) {
                count++;
            }
        }
        std::cout << count << '\n';
        return;
    }

    int compression_dist = t * t;
    
    std::vector<int> stone_final_pos;
    int current_pos = 0;
    int last_original_pos = 0;

    for (int stone_original_pos : stones) {
        int gap = stone_original_pos - last_original_pos;
        if (gap > compression_dist) {
            current_pos += compression_dist;
        } else {
            current_pos += gap;
        }
        stone_final_pos.push_back(current_pos);
        last_original_pos = stone_original_pos;
    }

    int final_l = current_pos;
    int remaining_gap = l - last_original_pos;
    if (remaining_gap > compression_dist) {
        final_l += compression_dist;
    } else {
        final_l += remaining_gap;
    }

    std::vector<bool> is_stone(final_l + t, false);
    for (int pos : stone_final_pos) {
        is_stone[pos] = true;
    }

    std::vector<int> dp(final_l + t, m + 1);
    dp[0] = 0;

    for (int i = 1; i < final_l + t; ++i) {
        for (int j = s; j <= t; ++j) {
            if (i >= j) {
                dp[i] = std::min(dp[i], dp[i - j]);
            }
        }
        if (is_stone[i]) {
            dp[i]++;
        }
    }

    int min_stones = m + 1;
    for (int i = final_l; i < final_l + t; ++i) {
        min_stones = std::min(min_stones, dp[i]);
    }

    std::cout << min_stones << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}