记录编号	223052	评测结果	AAAAAAATTT
题目名称	[USACO Mar09]餐厅清扫	最终得分	70
用户昵称	Satoshi	是否通过	未通过
代码语言	C++	运行时间	4.420 s
提交时间	2016-02-06 21:38:36	内存使用	0.66 MiB

#include <fstream>
#define N 40010
using namespace std;
ifstream in("cleanup.in");
ofstream out("cleanup.out");
int f[N]={0};
int c[N]={0};
bool l[N]={0};
int n,m,tot;
int ans=0;
int INF=(1<<28);
void read()
{
	int i;
	in>>n>>m;
	for(i=1;i<=n;i++)in>>c[i];
}
void work()
{
	int i,j;
	f[0]=0;
	for(i=1;i<=n;i++)f[i]=INF;
	l[0]=1;
	//for(i=1;i<=n;i++)out<<f[i]<<' ';
	//out<<endl;
	for(i=1;i<=n;i++)
	{
		tot=0;
		for(j=1;j<=m;j++)l[j]=0;
		if(!l[c[i]])
		{
			l[c[i]]=1;
			tot++;
		}
		for(j=i-1;j>=0;j--)
		{
			f[i]=min(f[i],f[j]+tot*tot);
			if(!l[c[j]])
			{
				l[c[j]]=1;
				tot++;
			}
			/*if(tot==m)
			{
				f[i]=min(f[i],tot*tot);
				break;
			}*/
		}
	}
	//for(i=1;i<=n;i++)out<<f[i]<<' ';
	//out<<endl;
	out<<f[n]<<endl;
}
int main()
{
	read();
	work();
	return 0;
}