{"trustable":true,"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":"\u003cp\u003eBạn được cho một mảng gồm \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e... \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Chi phí của một đoạn con là số cặp chỉ số không thứ tự trong đoạn con đó chứa các phần tử bằng nhau. Chia mảng cho trước thành \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e đoạn con không giao nhau sao cho tổng chi phí của chúng là nhỏ nhất có thể. Mỗi phần tử phải xuất hiện trong đúng một đoạn con.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003ek\u003c/i\u003e ≤ \u003ci\u003emin\u003c/i\u003e (\u003ci\u003en\u003c/i\u003e, 20))\u003c/span\u003e \u0026nbsp;— độ dài của mảng và số đoạn con cần chia mảng thành.\u003c/p\u003e\u003cp\u003eDòng tiếp theo chứa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\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)\u0026nbsp;— các phần tử của mảng.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn ra một số nguyên duy nhất: tổng chi phí của các đoạn con kết quả là nhỏ nhất có thể.\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\u003e7 3\n1 1 3 3 3 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\u003e10 2\n1 2 1 2 1 2 1 2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\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\u003e13 3\n1 2 2 2 1 2 1 1 1 2 2 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, tối ưu nhất là chia dãy thành ba đoạn con sau: \u003cspan class\u003d\"tex-span\"\u003e[1]\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e[1, 3]\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e[3, 3, 2, 1]\u003c/span\u003e. Chi phí tương ứng là \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e, do đó câu trả lời là \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, tối ưu nhất là chia dãy thành hai nửa bằng nhau. Chi phí cho mỗi nửa là \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ ba, tối ưu nhất là chia dãy thành ba đoạn con sau: \u003cspan class\u003d\"tex-span\"\u003e[1, 2, 2, 2, 1]\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e[2, 1, 1, 1, 2]\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e[2, 1, 1]\u003c/span\u003e. Chi phí tương ứng là \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e"}}]}