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 ) )
代码如下：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<queue> 7 #include<iostream> 8 #define INF 999999999999 9 #define LL long long 10 #define N 40004 11 #define Min(x,y) if(x>y) x=y 12 using namespace std ; 13 int n,m,pos[N],last[N],f[N],col; 14 int main(){ 15 scanf("%d%d",&n,&m); 16 m=min(int(sqrt(n)),m); 17 memset(pos,-1,sizeof pos); 18 for(int i=1;i<=n;i++){ 19 scanf("%d",&col); 20 if(i-1&&last[col]==i-1){ 21 f[i]=f[i-1]; 22 last[col]=i; 23 continue; 24 } 25 for(int j=m;j-1;j--) 26 if((pos[j]==-1&&pos[j-1]>last[col])||pos[j]>last[col]) 27 pos[j]=pos[j-1]; 28 pos[1]=i; 29 last[col]=i; 30 f[i]=f[i-1]+1; 31 for(int j=m; j ;j--) 32 if(pos[j]!=-1) 33 Min(f[i],f[pos[j]-1]+j*j); 34 } 35 printf("%d",f[n]); 36 }