首先不难写出 \(O(n^2)\) 的 dp。设当前在第 \(i\) 个位置，从前面选择一个位置 \(j\)，并加上 \([j+1,i]\) 这一段的贡献（可以预处理），取最小值即可。
#include <iostream>
#include <cstdio>
#include <map>using namespace std;map<int,int> vis;
int f[2001],g[2001][2001];
int n,a[2001];signed main()
{cin >> n;for( int i = 1 ; i <= n ; i ++ )cin >> a[i];for( int i = 1 ; i <= n ; i ++ ){vis.clear();for( int j = i ; j <= n ; j ++ ){g[i][j] = g[i][j - 1];if( !vis[a[j]] )vis[a[j]] = 1,g[i][j] ++;}}for( int i = 1 ; i <= n ; i ++ ){f[i] = g[1][i] * g[1][i];for( int j = 1 ; j < i ; j ++ )f[i] = min( f[i] , f[j] + g[j + 1][i] * g[j + 1][i] );}cout << f[n];return 0;
}
考虑优化。读题可以发现一个显然的性质，即答案一定不会超过 \(n\)（每个数据都为一个连续段）。因此对于任意一个连续段的种类数量都不应超过 \(\sqrt{n}\)，在 \(n=2\times 10^5\) 时为 \(448\) 左右。
不妨改变思路，以当前的 \(i\) 为右端点，枚举种类数量，并求出等于该种类数量的最左端点 \(j\)（这一段的贡献相同，取最左能保证前面的贡献尽可能小），从 \(j-1\) 转移即可。时间复杂度 \(O(n \sqrt{n} )\)。
如何动态维护每个最左端点？对于新加进来的 \(a_i\)，更新对应的计数器，同时将上一次的左端点向右移动至种类数量符合（类似双指针的思路）。由于最多有 \(\sqrt{n}\) 种数，在每个种类数量下每个 \(a_i\) 被更新 \(2\) 次，故时间复杂度也是 \(O( n \sqrt{n} )\)。
实现时一些注意点：
- 数组不要开 long long，否则会 MLE。
- \(a\) 数组先离散化，方便直接用数组统计，否则使用 map 可能会 TLE。
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>using namespace std;int cnt[200001][452];
int f[200001],tot[452];
int n,m,a[200001],b[200001],d[200001];signed main()
{cin >> n;for( int i = 1 ; i <= n ; i ++ )cin >> a[i],b[i] = a[i],f[i] = i;sort( b + 1 , b + n + 1 );m = unique( b + 1 , b + n + 1 ) - b - 1;for( int i = 1 ; i <= 450 ; i ++ )d[i] = 1;for( int i = 1 ; i <= n ; i ++ )a[i] = lower_bound( b + 1 , b + m + 1 , a[i] ) - b;for( int i = 1 ; i <= n ; i ++ ){for( int j = 1 ; j <= 450 ; j ++ ){if( !cnt[a[i]][j] ){tot[j] ++;cnt[a[i]][j] ++;}else cnt[a[i]][j] ++;while( tot[j] > j ){cnt[a[d[j]]][j] --;if( cnt[a[d[j]]][j] == 0 )tot[j] --;d[j] ++;}if( tot[j] == j )f[i] = min( f[i] , f[d[j] - 1] + j * j );//cout << i << ' ' << j << ' ' << d[j] << '\n';}
// cout << f[i] << endl;}cout << f[n];return 0;
}