HDU 5009 Paint Pearls （動态規劃）Paint Pearls

Problem Description

Lee has a string of n pearls. In the beginning, all the pearls have no color. He plans to color the pearls to make it more fascinating. He drew his ideal pattern of the string on a paper and asks for your help. 

In each operation, he selects some continuous pearls and all these pearls will be painted to their target colors. When he paints a string which has k different target colors, Lee will cost k2 points. 

Now, Lee wants to cost as few as possible to get his ideal string. You should tell him the minimal cost.

Input

There are multiple test cases. Please process till EOF.

For each test case, the first line contains an integer n(1 ≤ n ≤ 5×104), indicating the number of pearls. The second line contains a1,a2,...,an (1 ≤ ai ≤ 109) indicating the target color of each pearl.

Output

For each test case, output the minimal cost in a line.

Sample Input

3

1 3 3

10

3 4 2 4 4 2 4 3 2 2

Sample Output

2

7

Source

<a target="_blank" href="http://acm.hdu.edu.cn/search.php?%3C/p%3E%3Cp%3Efield=problem&amp;key=2014+ACM%2FICPC+Asia+Regional+Xi%27an+Online&amp;source=1&amp;searchmode=source">2014 ACM/ICPC Asia Regional Xi'an Online</a>

Recommend

hujie

題目大意：

           給定一系列的顔色。能夠劃分為随意多個随意大小的區間。每一個區間的花費為 區間顔色數的平方，問你總花費最小是多少？

解題思路：

         用動态規劃，雙向連結清單事實上就是維護前面不同的元素，同樣的元素删除。

解題代碼：

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5095919.html，如需轉載請自行聯系原作者