Problem
Chloe baru-baru ini memasang Zuma pada telefonnya. Pemain diberikan deretan n permata, ke-i yang mempunyai warna c
i. Tujuan permainan — musnahkan semua batu dalam beberapa saat yang mungkin.
Dalam satu saat, Chloe boleh memilih mana-mana subrentetan (jujukan batu bersebelahan) yang merupakan palindrom dan memadamkannya. Selepas mengeluarkan subrentetan ini, batu yang tinggal dialihkan untuk membentuk barisan berterusan semula. Berapakah bilangan saat minimum yang diperlukan untuk memusnahkan keseluruhan baris?
Ingat bahawa rentetan (atau subrentetan) ialah palindrom jika ia dibaca sama dari kiri ke kanan seperti dari kanan ke kiri. Dalam kes ini, ini bermakna bahawa warna batu pertama adalah sama dengan warna batu terakhir, warna kedua adalah sama dengan warna yang kedua dari belakang, dan seterusnya.
Input:
Baris pertama input mengandungi satu integer n (1 ≤ n ≤ 500) — bilangan batu dalam baris awal.
Baris kedua mengandungi n integer, ke-i yang sama dengan c
i (1 ≤ c
i ≤ n) &mdash ; warna batu ke-i pada baris awal.
Output:
Cetak satu integer — bilangan saat minimum yang diperlukan untuk mengeluarkan semua permata.
Contoh:
| Input |
Output |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Penjelasan:
Urutan dalam contoh ketiga ialah [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []