贪心、动态规划

由于颜色数对应的代价会平方级增长，每 $1$ 个元素分 $1$ 组是很优的。

观察样例，发现连续的 $5$ 个数被压到了一块，代价为 $4$，这个情况似乎有些复杂。

转念一想这又并不复杂，因为代价在平方级增长，某组的颜色数一旦超过 $\sqrt{n}$，这个组的代价就将飙升至 $n$ 以上，而一个元素一组的代价为 $n$，所以任何组的颜色数都不会超过 $\sqrt{n}$，这个强限制显然是解题的关键。

设计 $dp_i$ 为使得第 $i$ 个元素为最后一组的最后一个元素，且编号 $1 \sim i$ 的所有元素都完成分组需要的最小代价。如果位置 $j$ 的颜色 $col_j$ 是区间 $[1,i]$ 中最后出现的 $\sqrt{n}$ 种颜色之一并且 $j$ 是区间 $[1,i]$ 中最后一个颜色为 $col_j$ 的位置，就让 $j$ 转移到 $i$，符合条件的 $j$ 至多有 $\sqrt{n}$ 个。

使用链表维护最后出现的 $\sqrt{n}$ 种颜色及其出现位置，由于链表内部元素不重，可以 $O(1)$ 维护所有操作。动态规划转移时若当前元素是最后出现的第 $k$ 个元素，位置为 $p$，那么区间 $[p+1,i]$ 都不存在该元素以及出现更晚的其他元素，令 $dp_i \leftarrow \min(dp_i,dp_p + (k-1)^2)$。注意这样实际上是在完成前 $k-1$ 个元素向第 $i$ 个元素的转移，链表中最后一个元素是转移不到的，将链表元素个数限制开到大于 $\sqrt{n}$ 可以解决链表中元素个数达到上限时的问题。在位置 $0$ 加入一个颜色为 $0$ 的元素可以结算链表元素个数未达到上限时链表中的所有元素。

时间复杂度 $O(n \sqrt{n})$。

#include<bits/stdc++.h>
using namespace std;
constexpr int B=450;
unordered_map<int,list<pair<int,int>>::iterator> m;
int n,a[200'005],dp[200'005];
list<pair<int,int>> li;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(dp,63,sizeof(dp));
    li.push_front({0,0});
    dp[0]=0,m[0]=li.begin();
    for(int i=1;i<=n;i++){
        if(m.count(a[i])){
            li.erase(m[a[i]]);
            li.push_front({a[i],i});
            m[a[i]]=li.begin();
        }
        else{
            if(li.size()==B){
                m.erase(li.back().first);
                li.pop_back();
            }
            li.push_front({a[i],i});
            m[a[i]]=li.begin();
        }
        int cnt=0;
        for(auto [col,j]:li){
            ++cnt;
            dp[i]=min(dp[i],dp[j]+(cnt-1)*(cnt-1));
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}