本文共 1800 字，大约阅读时间需要 6 分钟。

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 k 2 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×10 4), indicating the number of pearls. The second line contains a 1,a 2,…,a n (1 ≤ a i ≤ 10 9) 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 很容易想到递推关系式dp[i]=min(dp[i],dp[j]+sum(j+1,i)^2)，sum(j+1,i)代表着从j+1~i不同数字的个数。 那么最主要的就是怎么去求这个sum？要是遍历的话肯定会超时，那么如何去优化呢？双端链表就有用处了。就像12222223333这样的数据，遍历到1之后，双端链表就直接跳跃到最后一个2了，然后就到了3，那么原来11位的数字就可以缩为3的了。 代码如下：

#include
   
    #define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxx=1e5+100;int pre[maxx],nxt[maxx],a[maxx];map
    
     mp;int dp[maxx];int n;int main(){
   	while(~scanf("%d",&n))	{
   		mp.clear();memset(dp,inf,sizeof(dp));dp[0]=0;		for(int i=1;i<=n;i++) scanf("%d",&a[i]);		for(int i=0;i<=n;i++) pre[i]=i-1,nxt[i]=i+1;		for(int i=1,tmp;i<=n;i++)//双端链表删除元素		{
   			if(!mp[a[i]]) mp[a[i]]=i;			else			{
   				tmp=mp[a[i]];				nxt[pre[tmp]]=nxt[tmp];				pre[nxt[tmp]]=pre[tmp];				mp[a[i]]=i;			}			for(int j=pre[i],cnt=0;~j;j=pre[j])			{
   				cnt++;				dp[i]=min(dp[i],dp[j]+cnt*cnt);				if(cnt*cnt>n) break;			}		}		printf("%d\n",dp[n]);	}}
    
   

努力加油a啊，(^o)/~

转载地址：http://jztvi.baihongyu.com/