Problem
کلویی اخیرا زوما را روی گوشی خود نصب کرده است. به بازیکن یک ردیف n جواهر داده می شود که i-امین آن دارای رنگ c
i است. هدف بازی — تمام سنگ ها را در کمترین ثانیه ممکن نابود کنید.
در یک ثانیه، کلوئه می‌تواند هر زیر رشته (توالی از سنگ‌های مجاور) را که یک پالیندروم است انتخاب کرده و آن را حذف کند. پس از حذف این زیر رشته، سنگ های باقی مانده جابجا می شوند تا دوباره یک ردیف پیوسته تشکیل شود. حداقل ثانیه های لازم برای از بین بردن کل خط چقدر است؟
به یاد بیاورید که یک رشته (یا زیر رشته) اگر از چپ به راست و از راست به چپ یکسان خوانده شود، یک پالیندروم است. در این صورت به این معنی است که رنگ سنگ اول با رنگ سنگ آخر، رنگ سنگ دوم برابر با سنگ ماقبل آخر و غیره است.
ورودی:
خط اول ورودی شامل یک عدد صحیح n (1 ≤ n ≤ 500) — تعداد سنگ های ردیف اولیه.
خط دوم شامل n عدد صحیح است که i ام آن برابر با c
i (1 ≤ c
i ≤ n) &mdash است. ; رنگ سنگ iام در ردیف اولیه.
خروجی:
چاپ یک عدد صحیح — حداقل تعداد ثانیه مورد نیاز برای حذف همه جواهرات.
مثال:
<بدن>
| ورودی |
خروجی |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
توضیحات:
دنباله در مثال سوم [1، 4، 4، 2، 3، 2، 1] است -> [1، 4، 4، 1] -> []