题目内容

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

输入描述

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

题解

题面分析

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

思路

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