Programozás‎ > ‎Feladatok‎ > ‎

Kilátás a tengerre

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