P2943 [USACO09MAR]Cleaning Up G

一句话题意：将一个数列分成若干段，每段的不和谐度为该段内不同数字数量的平方，求不和谐度之和的最小值。

令 (f_i) 表示前 (i) 个数的最小答案，很容易就能写出暴力转移方程：(f_i=min{f_j+sum(j,i)}(0leq j<i))。(sum(j,i)) 表示 (jsim i) 中不同数字的数量。

这样做是 (O(N^2)) 的，考虑优化。发现 (f) 数组是单调不降的，在 (sum(j,i)) 相同时，(j) 取最小最优。继续推性质，发现答案最大是 (N)（每个数都分一段），所以 (sum(j,i)) 最大取 (lfloorsqrt N floor) 否则显然不优。

然后就很简单了，我们对于 (sum(j,i)) 的每种取值都维护 (j) 的最小值即可。

所以做题要多推推性质啦。

时间复杂度 (O(Nsqrt N))。

code:

#include<bits/stdc++.h>
using namespace std;
#define N 40005
#define Db double
#define Min(x,y)((x)<(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
int f[N],last[N],que[205];
int main()
{
	int n,m,top,i,j,p;
	scanf("%d%d",&n,&m);
	top=int(sqrt(Db(n)));
	For(i,1,m)last[i]=-1;
	For(i,1,n)
	{
		f[i]=i;
		scanf("%d",&p);
		if(last[p]<que[1])
		For(j,1,top)que[j-1]=que[j];
		else
		{
			For(j,1,top)
			if(que[j]==last[p])break;
			while(j<top)que[j]=que[j+1],j++;
		}
		que[top]=i;
		For(j,1,top)f[i]=Min(f[que[j-1]]+(top-j+1)*(top-j+1),f[i]);
		last[p]=i;
	}
	cout<<f[n];
	return 0;
}