[CSP-X2020 山东] 勇敢的津津

Luogu
IDLGB4089
Time1000ms
Memory128MB
DifficultyP2
动态规划 DP贪心2020山东CSP-X 小学组
津津是个勇敢的孩子,总是做一些挑战自己的事情。一天津津来到一条宽为 $L$ 米的小河边,河道的一边到另一边需要途径 $N$ 块较大的石墩,每块石墩到这一边岸边之间距离 $d_i$ 米(石墩不占距离,只考虑石墩的中间点到这一边岸边之间距离)。津津想踩着这些石墩从小河的这一边跳到另一边(不落入水中),一次可以跳过几块石墩。已知津津每次最多跳 $M$ 米的距离,那么津津最少跳几次就能从这一边跳到另一边? ## Input 第一行包含三个整数 $L,N,M$,分别小河的宽度、石墩数和津津跳的最远距离。 接下来 $N$ 行,每行一个整数,第 $i$ 行的整数 $d_i(0\lt d_i \lt L)$,表示第 $i$ 块石墩与这一边岸边的距离,保证石墩之间的距离和最靠边的石墩到这一边岸边的距离小于等于 $M$。这些石墩按与起点距离从小到大的顺序给出,且不会有两个石墩出现在同一个位置。 ## Output 一个整数,即最少的跳跃次数。 [samples] ## Note 【样例解释】 样例一:津津可以从岸边跳到距离为 $2$ 的石墩上,然后跳到距离为 $4$ 的石墩上,再跳到距离为 $6$ 的石墩上,再跳到距离为 $8$ 的石墩上,最后跳到对岸。总共 $5$ 跳跃。 样例二:津津可以从岸边跳到距离为 $2$ 的石墩上,然后跳到距离为 $11$ 的石墩上,再跳到距离为 $21$ 的石墩上,最后跳到对岸。总共 $4$ 跳跃。 【数据范围】 对于 $30\%$ 的数据,$1\leq N\leq 10$。 对于 $50\%$ 的数据,$1\leq N\leq 100$。 对于 $100\%$ 的数据,$1\leq N\leq 500$,$1\leq M,L\leq 10^6$。
Samples
Input #1
10 4 2
2
4
6
8
Output #1
5
Input #2
25 5 10
2
11
14
17
21
Output #2
4
API Response (JSON)
{
  "problem": {
    "name": "[CSP-X2020 山东] 勇敢的津津",
    "description": {
      "content": "津津是个勇敢的孩子,总是做一些挑战自己的事情。一天津津来到一条宽为 $L$ 米的小河边,河道的一边到另一边需要途径 $N$ 块较大的石墩,每块石墩到这一边岸边之间距离 $d_i$ 米(石墩不占距离,只考虑石墩的中间点到这一边岸边之间距离)。津津想踩着这些石墩从小河的这一边跳到另一边(不落入水中),一次可以跳过几块石墩。已知津津每次最多跳 $M$ 米的距离,那么津津最少跳几次就能从这一边跳到另一边?",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4089"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "津津是个勇敢的孩子,总是做一些挑战自己的事情。一天津津来到一条宽为 $L$ 米的小河边,河道的一边到另一边需要途径 $N$ 块较大的石墩,每块石墩到这一边岸边之间距离 $d_i$ 米(石墩不占距离,只考虑石墩的中间点到这一边岸边之间距离)。津津想踩着这些石墩从小河的这一边跳到另一边(不落入水中),一次可以跳过几块石墩。已知津津每次最多跳 $M$ 米的距离,那么津津最少跳几次就能从这一边跳到另一边?...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments