Ocean View egy kis város a tengerparton. Egyetlen utcája a Döbbenetes utca, amely a tengerparttól a hegyek felé vezet, és az utca házai 1-től N-ig vannak számozva. (1 van a tengerparton.)
A lakók szeretnének kilátni a tengerre, de sajnos vannak házak, amelyek eltakarják mások elől a kilátást. Ház A eltakarja a kilátást B elől, ha A < B és A legalább olyan magas, mint B.
Belefáradva az állandó panaszáradatba, Ocean View kormányzója úgy döntött, hogy megoldja a problémát és kedvenc kormányzati eszközéhez, az erőszakhoz folyamodik. Parancsot ad néhány ház lerombolására, hogy a többiek kilátását biztosítsa. Persze nem akar túl sok házat lerombolni, mert fél, hogy esetleg forradalom törne ki, ezért minimalizálni szeretné a lebontandó házak számát.
Feladat
Írjunk programot, ami megadja, hogy legkevesebb hány ház lebontásával lehet elérni, hogy a megmaradt házak lakói kilássanak a tengerre.
Bemenet
A bemenet első sora a tesztesetek T számát adja meg (T <= 100). Ezután T teszteset jön, két-két sorban. Az első sor mindig a házak számát tartalmazza (1 <= N <= 1000), a második pedig az N ház magasságát (1 és 1000 közötti egészek, szóközzel elválasztva).
Kimenet
A kimenet egyetlen sorába a minimálisan lebontandó házak számát kell írni.
Példa
Bemenet |
Kimenet |
4 4 1 4 3 3 5 3 4 6 7 10 4 4 3 2 1 5 4 5 6 1 7
| Case #1: 2 Case #2: 0 Case #3: 3 Case #4: 1
|
Tesztadatok
Címkék
A feladat forrása: Google Code Jam 2013 - veteran competition
Algoritmusok: dinamikus programozás
megoldás |