题解

题面分析

小明计划在假期安排一次自驾旅行。从小明所在的城市，到旅行目的地，仅有一条高速公路，该高速公路上有 $N$ 个服务区，每个服务区都提供了餐饮、休息等服务，需要一定的花费。为了避免疲劳驾驶，每经过 $M$ 个服务区，至少必须进入其中的某个服务区，停车休息一次。休息时，需要一定的花费。请帮小明安排一个服务区休息计划，使其在服务区的总花费最少。

思路

本题要求在 $N$ 个服务区中安排休息点，使得每经过连续 $M$ 个服务区至少休息一次，并且总花费最小。可以采用动态规划的方法来解决。具体步骤如下：

1. 定义状态：

   • 定义 dp[i] 表示在第 i 个服务区之前（即前 i 个服务区）满足条件的最小总花费。
   • 为了更清晰地表示状态，我们还可以引入一个辅助数组 last_rest[i]，表示在第 i 个服务区之前，最后一次休息的位置。

2. 状态转移：

   • 对于每个服务区 i，我们需要考虑在前 M 个服务区内的任意一个位置 j 休息，然后在 i 处休息。因此，状态转移方程为：
   • 其中，cost[j-1] 表示在第 j 个服务区休息的花费（数组下标从 0 开始）。

3. 初始化：

   • dp[0] = 0，表示在起点没有花费。
   • 对于 1 ≤ i ≤ M，dp[i] = min(cost[0..i-1])，因为在前 M 个服务区内至少需要一个休息点。

4. 最终结果：

   • 为了满足最后的 M 个服务区中至少休息一次的要求，最终结果应为 dp[N]，即在前 N 个服务区内满足条件的最小总花费。

优化思路

上述动态规划的时间复杂度为 $O(N \times M)$，当 $N$ 和 $M$ 较大时，可能会导致运行时间较长。为了优化时间复杂度，可以采用以下方法：

1. 滑动窗口最小值：

   • 使用滑动窗口维护前 M 个 dp[j-1] 的最小值，从而将状态转移的时间复杂度降为 $O(N)$。
   • 具体做法是使用双端队列（deque）来维护一个单调递增的队列，队列中存储的是可能的 j-1 索引，并保证队列头部始终是最小的 dp[j-1]。

2. 实现细节：

   • 在遍历每个服务区 i 时，首先移除队列中不在 [i-M, i-1] 范围内的元素。
   • 然后，当前 dp[i] 就是队列头部元素对应的 dp[j-1] 加上当前服务区的费用 cost[i-1]。
   • 最后，维护队列的单调性，将当前 i 插入队列，并移除所有在 dp[i] 之后比 dp[i] 大的元素。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> cost(N);
    for(auto &x: cost) cin >> x;
    // dp[i]表示在第i个服务区休息时的最小总花费
    vector<long long> dp(N+1, 1e18);
    dp[0] = 0;
    // 使用双端队列维护窗口内的最小dp[j]
    deque<int> dq;
    dq.push_back(0);
    for(int i=1; i<=N; ++i){
        // 保证窗口内的j满足i - j <= M
        while(!dq.empty() && i - dq.front() > M){
            dq.pop_front();
        }
        if(!dq.empty()){
            dp[i] = dp[dq.front()] + cost[i-1];
        }
        // 保持队列单调递增
        while(!dq.empty() && dp[i] <= dp[dq.back()]){
            dq.pop_back();
        }
        dq.push_back(i);
    }
    // 最终结果是在最后M个dp[j]中取最小值
    long long res = 1e18;
    for(int i=max(1, N-M+1); i<=N; ++i){
        res = min(res, dp[i]);
    }
    cout << res;
}

python

import sys
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N, M = map(int, data[:2])
    cost = list(map(int, data[2:2+N]))
    INF = float('inf')
    dp = [INF]*(N+1)
    dp[0] = 0
    dq = deque()
    dq.append(0)
    for i in range(1, N+1):
        # 移除不在窗口内的j
        while dq and i - dq[0] > M:
            dq.popleft()
        if dq:
            dp[i] = dp[dq[0]] + cost[i-1]
        # 保持队列单调递增
        while dq and dp[i] <= dp[dq[-1]]:
            dq.pop()
        dq.append(i)
    # 最终结果是在最后M个dp[j]中取最小值
    res = INF
    start = max(1, N-M+1)
    for j in range(start, N+1):
        res = min(res, dp[j])
    print(int(res))

if __name__ == "__main__":
    main()

java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().trim().split("\\s+");
        int N = Integer.parseInt(first[0]);
        int M = Integer.parseInt(first[1]);
        String[] second = br.readLine().trim().split("\\s+");
        int[] cost = new int[N];
        for(int i=0;i<N;i++) cost[i] = Integer.parseInt(second[i]);
        long INF = Long.MAX_VALUE;
        long[] dp = new long[N+1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(0);
        for(int i=1;i<=N;i++){
            // 移除不在窗口内的j
            while(!dq.isEmpty() && i - dq.peekFirst() > M){
                dq.pollFirst();
            }
            if(!dq.isEmpty()){
                dp[i] = dp[dq.peekFirst()] + cost[i-1];
            }
            // 保持队列单调递增
            while(!dq.isEmpty() && dp[i] <= dp[dq.peekLast()]){
                dq.pollLast();
            }
            dq.addLast(i);
        }
        // 最终结果是在最后M个dp[j]中取最小值
        long res = INF;
        int start = Math.max(1, N-M+1);
        for(int j=start; j<=N; j++){
            res = Math.min(res, dp[j]);
        }
        System.out.println(res);
    }
}

题目内容

小明计划在假期安排一次自驾旅行。从小明所在的城市，到旅行目的地，仅有一条高速公路，该高速公路上有 $N$ 个服务区，每个服务区都提供了餐饮、休息等服务，需要一定的花费。为了避免疲劳驾驶，每经过 $M$ 个服务区，至少必须进入其中的某个服务区，停车休息一次。休息时，需要一定的花费。请帮小明安排一个服务区休息计划，使其在服务区的总花费最少。

输入描述

第一行:两个整数 $N$ ，$M$ 。其中 $N$ 表示服务区的数量，$M$ 表示经过连续 $M$ 个服务区，必须至少停车休息一次。

第二行:包含 $N$ 个整数的数组。第 $i$ 个元素，表示第 $i$ 个服务区休息时需要的费用(假定在服务区 $i$ 停车休息，一定会消费该服务区对应的费用)其中:

• $0<N<= 10000$

• $0<M <= 50$

输出描述

一行，表示在服务区休息的最小总花费。

样例1

输入

5 3
5 6 9 10 6

输出

9

说明

在第 $3$ 个服务区休息一次，花费为 $9$ 最少。

样例2

输入

4 2
3 2 2 5

输出

4

说明

在第 $2$ 个服务区和第 $3$ 个服务区休息，总花费为 $2+2=4$ 最少