Description：

有 $n$ 个数字，每一段的不和谐度是这个区间内不同数字个数的平方，求一种划分方案最小化不和谐度的和。

$1\le n \le 40000$

Solution：

首先如果每一个数划分为一段，那么总的不和谐度就是 $n$ ，所以最终的最小不和谐度一定不大于 $n$ ，也就是说一段最多只能有 $\sqrt n$ 个不同的数字，又看到这题数据范围，复杂度应该是 $O(n\sqrt n)$ 。

$f[i]$ 表示划分到 $i$ 的代价， $b[j]$ 为从 $b[j]+1$ 到 $i$ 共有 $j$ 种数字的最靠前的位置，因为同样数字种数，越长肯定有可能更优， $c[j]$ 表示 $b[j]+1$ 到 $i$ 的数字种数，用来维护 $b$ ， $pre[a[i]]$ 表示数字 $a[i]$ 的上一个位置。

先说转移， $f[i]=\min(f[b[j]]+j\times j)$ 。

然后问题就变成了如何维护 $b$ 数组，当 $i$ 后移一位时，如果之前 $b[j]+1$ 到 $i-1$ 这段区间中没有出现过，这个可以用 $pre$ 判断，那么 $++c[j]$ ，如果 $c[j]>j$ ，就不断后移 $b[j]$ 直到删去了一个只在 $[b[j]+1,i]$ 中出现了一次的数字，这个也可以用 $pre$ 判断。

一般不同数字个数的题都要维护一个 $pre$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 40010

int a[MAXN];

int f[MAXN];

int b[MAXN],c[MAXN];

int s[MAXN],tot = 0;

int pre[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	memset(f,0x3f,sizeof(f));

	f[0] = 0;

	m = sqrt(n);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

			if(pre[a[i]] <= b[j])

				++c[j];

		pre[a[i]] = i;

		for(int j = 1;j <= m;++j)

		{

			if(c[j] > j)

			{

				++b[j];

				while(pre[a[b[j]]] > b[j])++b[j];

				c[j] = j;

			}

		}

		for(int j = 1;j <= m;++j)

			f[i] = min(f[i],f[b[j]] + j * j);

	}

	cout << f[n] << endl;

	return 0;

}