首先把具有相同颜色的点缩成一个点，即数据离散化。
然后使用dp[i]表示涂满前i个点的最小代价。对于第i+1个点，有两种情况：
1)自己单独涂，即dp[i+1] = dp[i] + 1
2)从第k个节点之后(不包括k)到第i+1个节点一次涂完，且一起涂的节点共有num种颜色，即dp[i+1] = dp[k] + num * num
从而可以得到状态转移方程dp[i+1] = min(dp[i], dp[k] + num * num)
但是如果从后往前遍历每一个k，会超时。
因此我们可以使用双向链表来把每种颜色最后出现的位置穿起来。对于每一个新加入的点，如果该点颜色没出现过，那么把它加入到双向链表的结尾。如果该点出现过，把它最后出现的位置从双向链表中删除，并把最新的位置加入到双向链表结尾。
需要注意的是要建立一个头节点，使得第一个节点不会因为后面出现了同样的颜色而被删除，从而无法计算从头到尾一次性涂完的情况。
第二个要注意的是如果num * num 已经大于了每个节点单独涂的代价 i，那么就没有必要再往前查找了。
代码如下：
#define MAXN 50005
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <map>
#include <limits.h> using namespace std;
int arr[MAXN];//输入
int l[MAXN];//记录前一个最后出现的颜色的位置
int r[MAXN];//记录后一个最后出现颜色的位置
int dp[MAXN];//dp[i]表示涂到第i个节点最小的代价
int m;//离散化后数组的长度 void solve()
{
map<int, int> exist;//map 存储出当前现过得颜色中，最后出现的位置
int last = ;//双向链表尾
l[] = -;//头节点
r[] = ;//头节点
l[] = ;
exist[arr[]] = ;
dp[] = ;
dp[] = ; for( int i = ; i < m ; i++ )
{
if( exist.count(arr[i]) == )
{
r[last] = i;//添加到尾部
l[i] = last;
last = i;
exist[arr[i]] = i;
}
else
{
int tmp = exist[arr[i]];
r[l[tmp]] = r[tmp];//删除tmp
l[r[tmp]] = l[tmp];//删除tmp
r[last] = i;
l[i] = last;
last = i;
exist[arr[i]] = i;
} int k = last;
dp[i] = dp[i-]+;
int num = ;
while( l[k] >= )
{
dp[i] = min(dp[i], dp[l[k]] + num*num);
num++;
k = l[k];
if( num * num > i )//剪枝
{
break;
}
}
}
printf("%d\n", dp[m-]);
} int main(int argc, char *argv[])
{
int n;
while(scanf("%d", &n) != EOF)
{
int a;
m = ;
for( int i = ; i <= n ; i++ )//从1开始，位置0是头节点
{
scanf("%d", &a);
if( i == )
{
arr[m++] = a;
}
else if( arr[m-] != a )//合并相同颜色的节点，离散化
{
arr[m++] = a;
}
}
solve();
}
return ;
}