记录编号	423270	评测结果	AAAAAAAAAA
题目名称	[USACO Mar09]餐厅清扫	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.106 s
提交时间	2017-07-11 14:36:39	内存使用	4.10 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e5+10;
int n,m,size,p[N],dp[N];
//dp[i]表示前i头奶牛吃完后的最小用时
int last[N],fa[N],Min[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
	freopen("cleanup.in","r",stdin);
	freopen("cleanup.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&p[i]);
	for (int i=1;i<=n;i++) fa[i]=i,dp[i]=Min[i]=1e9;
	size=sqrt(n);
	for (int i=1;i<=n;i++){
		Min[i]=min(Min[i],dp[i-1]);
		if (last[p[i]]){
			int pos=last[p[i]],u=find(pos),v=find(pos+1);
			fa[v]=u;
			Min[u]=min(Min[u],Min[v]);
		}
		last[p[i]]=i;
		for (int cnt=1,j=i;cnt<=size;cnt++,j--){
			j=find(j);
			dp[i]=min(dp[i],Min[j]+cnt*cnt);
			if (j==1) break;
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}