Description
从前奶牛是不挑食的，但现在世道变了，她们变得非常挑剔。牧场里有N头奶牛，约翰 要向她们提供M种食物，第i头奶牛只会吃Pi号食物。
约翰每天都要打扫食槽，这件事非常累。奶牛沿着食槽排成一条直线，约翰在打扫时， 可以将食槽分割成若干个区间，如果一段区间中有K种不同的食物，那么这段区间打扫的时 间就是K2。请帮助约翰计划一下，怎么样才能使打扫整个食槽的时间最少。
Input Format
第一行：两个用空格分开的整数：N和M，1 ≤ M ≤ N ≤ 40000
第二行到N + 1行：第i + 1行有一个整数Pi，1 ≤ Pi ≤ M
Output Format
第一行：单个整数，表示约翰完成打扫的最短时间
-----------------------------------------------------------
正解 = 动归- =
考虑裸Dp ：
状态 ：f[i]表示到 i 这个头牛时，打少至少需要的时间
转移 ：f[i]=min(f[j],cal(j+1,i)^2) (cal(j+1,i)=>从 j+1 到 i ) 食物种类数。
直接进行计算需要 O（n^3）
预处理cal 则需要 O (n^2)
对于 N 的数据范围，这两种算法显然都不尽如人意
考虑一种新的转移
现看成一个染色问题- =，
设数为 pos[i] 为取 i 种颜色时，到当前点最远的区间，
则 f[i]=min（f[pos[j]-1]+j*j）,
由于一个区间内的颜色不应超过 sqrt( n ），
所以转移的复杂度为 O( sqrt( n ) ) ,
考虑对 pos 的维护( 刚开始想歪了- =，谢谢lazycal大神指导)
当加尽一个颜色，显然只有从上一个当前这个颜色的点到它之间的颜色数会发生改变，
设数组last[i]表示 i 颜色的上一个位置，如果pos落在这之间则 pos[j]=pos[j-1]
注意处理 j 为当前最多颜色的情况。
维护复杂度 O( sqrt( n ) )；
总复杂度： O( n sqrt( n ) )
代码如下：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<iostream>
#define INF 999999999999
#define LL long long
#define N 40004
#define Min(x,y) if(x>y) x=y
using namespace std ;
int n,m,pos[N],last[N],f[N],col;
int main(){
scanf("%d%d",&n,&m);
m=min(int(sqrt(n)),m);
memset(pos,-,sizeof pos);
for(int i=;i<=n;i++){
scanf("%d",&col);
if(i-&&last[col]==i-){
f[i]=f[i-];
last[col]=i;
continue;
}
for(int j=m;j-;j--)
if((pos[j]==-&&pos[j-]>last[col])||pos[j]>last[col])
pos[j]=pos[j-];
pos[]=i;
last[col]=i;
f[i]=f[i-]+;
for(int j=m; j ;j--)
if(pos[j]!=-)
Min(f[i],f[pos[j]-]+j*j);
}
printf("%d",f[n]);
}