题解 | 过河

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 2005;
const int MAXM = 105;
const int INF = 0x7f7f7f7f;

class Solution {
private:
    int dp[MAXN];
    int idx[MAXN + 1];
    int stone[MAXM];
    
public:
    Solution() {
        memset(dp, 0, sizeof(dp));
        memset(idx, 0, sizeof(idx));
        memset(stone, 0, sizeof(stone));
    }
    
    int solve(int L, int S, int T, int M, int stones[]) {
        // 复制石头位置
        for(int i = 1; i <= M; i++) {
            stone[i] = stones[i-1];
        }

        // 压缩状态空间
        sort(stone + 1, stone + M + 1);
        stone[++M] = L;  // 添加终点
        int l = 0;  // 压缩后的长度
        memset(idx, 0, sizeof(idx));
        for(int i = 1; i <= M; i++) {
            int dis = stone[i] - stone[i - 1];
            if(dis > T) {
                l += dis % T + T;
            } else {
                l += dis;
            }
            idx[l] = 1;
        }

        // 动态规划求解
        int Length = l + T;
        memset(dp, INF, sizeof(dp));
        dp[0] = 0;
        
        for(int i = 1; i < Length; i++) {
            for(int j = S; j <= T; j++) {
                if(i >= j) {
                    dp[i] = min(dp[i], dp[i - j] + idx[i - j]);
                }
            }
        }

        // 寻找最优解
        int result = INF;
        for(int i = l; i < Length; i++) {
            result = min(result, dp[i]);
        }
        
        return result;
    }
};

int main() {
    int L, S, T, M;
    scanf("%d", &L);
    scanf("%d%d%d", &S, &T, &M);
    
    int stones[MAXM];
    for(int i = 0; i < M; i++) {
        scanf("%d", &stones[i]);
    }
    
    Solution solution;
    printf("%d\n", solution.solve(L, S, T, M, stones));
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private static final int MAXN = 2005;
        private static final int MAXM = 105;
        private static final int INF = 0x7f7f7f7f;
        
        private int[] dp = new int[MAXN];
        private int[] idx = new int[MAXN + 1];
        private int[] stone = new int[MAXM];
        
        public int solve(int L, int S, int T, int M, int[] stones) {
            // 复制石头位置
            for(int i = 1; i <= M; i++) {
                stone[i] = stones[i-1];
            }

            // 压缩状态空间
            Arrays.sort(stone, 1, M + 1);
            stone[++M] = L;  // 添加终点
            int l = 0;  // 压缩后的长度
            Arrays.fill(idx, 0);
            for(int i = 1; i <= M; i++) {
                int dis = stone[i] - stone[i - 1];
                if(dis > T) {
                    l += dis % T + T;
                } else {
                    l += dis;
                }
                idx[l] = 1;
            }

            // 动态规划求解
            int Length = l + T;
            Arrays.fill(dp, INF);
            dp[0] = 0;
            
            for(int i = 1; i < Length; i++) {
                for(int j = S; j <= T; j++) {
                    if(i >= j) {
                        dp[i] = Math.min(dp[i], dp[i - j] + idx[i - j]);
                    }
                }
            }

            // 寻找最优解
            int result = INF;
            for(int i = l; i < Length; i++) {
                result = Math.min(result, dp[i]);
            }
            
            return result;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt();
        int S = sc.nextInt();
        int T = sc.nextInt();
        int M = sc.nextInt();
        
        int[] stones = new int[M];
        for(int i = 0; i < M; i++) {
            stones[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(L, S, T, M, stones));
    }
}

from typing import List
import sys

class Solution:
    def __init__(self):
        self.MAXN = 2005
        self.MAXM = 105
        self.INF = 0x7f7f7f7f
        self.dp = [0] * self.MAXN
        self.idx = [0] * (self.MAXN + 1)
        self.stone = [0] * self.MAXM
    
    def solve(self, L: int, S: int, T: int, M: int, stones: List[int]) -> int:
        # 复制石头位置
        for i in range(M):
            self.stone[i + 1] = stones[i]

        # 压缩状态空间
        self.stone[1:M+1] = sorted(self.stone[1:M+1])
        M += 1
        self.stone[M] = L  # 添加终点
        l = 0  # 压缩后的长度
        self.idx = [0] * (self.MAXN + 1)
        for i in range(1, M + 1):
            dis = self.stone[i] - self.stone[i - 1]
            if dis > T:
                l += dis % T + T
            else:
                l += dis
            self.idx[l] = 1

        # 动态规划求解
        Length = l + T
        self.dp = [self.INF] * self.MAXN
        self.dp[0] = 0
        
        for i in range(1, Length):
            for j in range(S, T + 1):
                if i >= j:
                    self.dp[i] = min(self.dp[i], self.dp[i - j] + self.idx[i - j])

        # 寻找最优解
        result = self.INF
        for i in range(l, Length):
            result = min(result, self.dp[i])
            
        return result

def main():
    input = sys.stdin.buffer.readline
    L = int(input())
    S, T, M = map(int, input().split())
    stones = list(map(int, input().split()))
    
    solution = Solution()
    print(solution.solve(L, S, T, M, stones))

if __name__ == "__main__":
    main()