Programozás‎ > ‎Feladatok‎ > ‎

Favágás

Egy favágónak ki kell vágnia N fát, amelyek egy sorba vannak ültetve, egymástól egyenlő távolságra.
A kivágott fa jobbra vagy balra dőlhet, és újabb fákat dönthet ki (amelyek a dominó-hatásnak megfelelően megint újabb fákat dönthetnek ki...). Melyik fákat érdemes kivágni, ha minimális vágással szeretnénk teljesíteni a feladatot? 

Feladat

Írjunk programot, ami meghatározza, hogy legkevesebb hány fa kivágással dönthető ki az összes fa, és meg is ad egy optimális kivágási tervet!

Bemenet

A bemenet első sora a fák N számát adja meg (1 <= N <= 1000000). A második sorban a fák magassága van felsorolva.

A dominó-hatás leírása

  • Ha egy H[i] magasságú fát balra döntünk, akkor kidönti az összes olyan j indexű fát, amire i-H[i]< j < i.
  • Ha az első fát balra döntöttük, akkor az összes fa balra dől, ami érintett a dominó-hatásban.
  • Ha jobbra döntjük a H[i] magasságú fát, akkor az i < j < i+H[i] sorszámú fákat dönti ki közvetlenül.
  • Egy fát csak egyszer lehet kidönteni.

Kimenet

Az első sorba a minimálisan szükséges vágás számát írjuk ki, a következő sorba pedig a kivágandó fák sorszámát. Az indexelés 1-től kezdődik! A balra döntött fák sorszámát negatív előjellel kell kiírni.

Példa

Bemenet  Kimenet
5
1 2 3 1 1
2
3 -2

vagy

2
1 2


Tesztadatok

Címkék

A feladat forrása: BME 24-órás programozói verseny, 2012 EC
Algoritmusok: 

megoldás