Farmer Ron au Colorado construit une station de ski pour ses vaches, avec budget pour une seule remontée. Le monorail relie un support de béton initial au final par des supports intermédiaires, chacun de hauteur0 au-dessus du sol. Un segment droit d’acier relie chaque paire voisine et doit partout rester au-dessus du sol.

Économe, FR minimise les supports. Il a relevé $N$ parcelles égales $(2 \le N \le 5,000)$ avec hauteur entière $H$ $(0 \le H \le 1,000,000,000)$. La sécurité impose une distance voisine au plus $K$ unités $(1 \le K \le N - 1)$. L’acier est rigide et droit.

Calculez le minimum de supports : acier entièrement au-dessus ou tangent au sol, distance horizontale voisine au plus $K$, supports sur les première et dernière parcelles.

Entrée

• Ligne $1$ : deux entiers séparés par un espace $N$, $K$.
• Lignes $2..N+1$ : ligne $i+1$ contient la hauteur entière de la parcelle $i$.

Sortie

• Ligne $1$ : un entier, le minimum de pylônes sous ces contraintes.

Exemples

Entrée 1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

Sortie 1

5

Remarque

5 supports en1, 5, 7, 9, 13. L’acier touche le sol à4 endroits :1–5, 5–7, 7–9, 12–13.

4 supports en1, 5, 9, 13 placent l’acier sous terre de5 à9. En1, 7, 13 il reste au-dessus mais7 et13 sont séparés de plus de4 horizontalement. Moins de5 supports avec distances voisines au plus4 est impossible.

Source originale : https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

Auteur du problème : Adam Rosenfield, 2004