Problem
Chloe kısa süre önce telefonuna Zuma'yı yükledi. Oyuncuya, i'de biri c
i rengine sahip n adet taş verilir. Oyunun amacı — mümkün olan en kısa sürede tüm taşları yok edin.
Bir saniyede, Chloe bir palindrom olan herhangi bir alt diziyi (bitişik taşlardan oluşan bir dizi) seçip onu silebilir. Bu alt dizi kaldırıldıktan sonra, kalan taşlar tekrar sürekli bir sıra oluşturacak şekilde kaydırılır. Tüm satırı yok etmek için gereken minimum saniye sayısı nedir?
Bir dizenin (veya alt dizenin), soldan sağa ve sağdan sola aynı şeyi okuması durumunda bir palindrom olduğunu hatırlayın. Bu durumda, bu, ilk taşın renginin son taşın rengine eşit olması, ikincinin renginin sondan bir önceki taşın rengine eşit olması vb.
Giriş:
Girişin ilk satırı tek bir tam sayı n (1 ≤ n ≤ 500) içerir — ilk sıradaki taş sayısı.
İkinci satır, i'incisi c
i'ye eşit olan n tam sayı içerir (1 ≤ c
i ≤ n) &mdash ; ilk sıradaki i'inci taşın rengi.
Çıktı:
Tek bir tamsayı yazdır — tüm mücevherleri kaldırmak için gereken minimum saniye sayısı.
Örnekler:
| Giriş |
Çıktı |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Açıklamalar:
Üçüncü örnekteki dizi [1, 4, 4, 2, 3, 2, 1] -->; [1, 4, 4, 1] -> []