{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"Gần đây, Genos đã cài đặt trò chơi Zuma trên điện thoại di động của mình. Trong Zuma, có một hàng gồm \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e viên ngọc, trong đó viên thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e có màu là \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Mục tiêu của trò chơi là phá hủy toàn bộ hàng ngọc càng sớm càng tốt.\n\nTrong một giây, Genos có thể chọn một chuỗi con liên tục các viên ngọc có màu đối xứng và loại bỏ chúng khỏi hàng. Sau khi chuỗi con bị loại bỏ, các viên ngọc còn lại sẽ được sắp xếp lại thành một hàng mới. Số giây tối thiểu cần để phá hủy toàn bộ hàng là bao nhiêu?\n\nChúng tôi nhắc lại rằng một chuỗi (hoặc chuỗi con) được gọi là đối xứng nếu nó có thể đọc từ trước ra sau và từ sau ra trước là giống nhau. Trong trường hợp của chúng tôi, điều này có nghĩa là màu của viên ngọc đầu tiên bằng màu của viên ngọc cuối cùng, màu của viên ngọc thứ hai bằng màu của viên ngọc thứ hai từ cuối cùng, và tiếp tục như vậy."}},{"title":"Đầu vào","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa một số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 500\u003c/span\u003e) — Số lượng viên ngọc.\u003c/p\u003e\u003cp\u003eDòng thứ hai chứa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e số nguyên được phân tách bằng dấu cách, trong đó số nguyên thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e là \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — Màu của viên ngọc thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eĐầu ra là một số nguyên — Số giây tối thiểu cần để phá hủy toàn bộ hàng ngọc.\u003c/p\u003e"}},{"title":"Ví dụ 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\n1 4 4 2 3 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Lưu ý","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ thứ nhất, Genos có thể phá hủy toàn bộ hàng trong một giây.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, Genos chỉ có thể phá hủy một viên ngọc mỗi lần, do đó cần ba giây để phá hủy ba viên ngọc.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ ba, để đạt được thời gian tối ưu là hai giây, đầu tiên Genos phá hủy chuỗi con đối xứng \u003cspan class\u003d\"tex-font-style-tt\"\u003e4 4\u003c/span\u003e, sau đó phá hủy chuỗi con đối xứng \u003cspan class\u003d\"tex-font-style-tt\"\u003e1 2 3 2 1\u003c/span\u003e.\u003c/p\u003e"}}]}