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 | 
2004-2016 BDG algoritmus szakkör