转载请注明出处：

 

1584: [Usaco2009 Mar]Cleaning Up 打扫卫生

Time Limit: 10 Sec  

Memory Limit: 64 MB

Submit: 550  

Solved: 382

Description

有N头奶牛，每头那牛都有一个标号Pi，1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有k个不同的数，那不河蟹度为k*k。那总的不河蟹度就是所有段的不河蟹度的总和。

Input

第一行：两个整数N，M

第2..N+1行：N个整数代表每个奶牛的编号

Output

一个整数，代表最小不河蟹度

Sample Input

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

Sample Output

11

题解：

我们很容易想到n^2的dp，f[i]=min{f[j]+pos[j]^2}(pos[j]指的是从j到i不同标号的种类数)。

显然，单个一段的种类数是不会超过n^(1/2)的，因为如果超过，不如直接每个自成一段，还是n。

我们还可以想到，如果对于一个i，pos[j1]=pos[j2]，那我们肯定又前面的转移过来。

所以问题就转化成了如何记录pos值相同时最靠前的位置。

我们可以记录一个数组pre，表示a[i]上次出现的位置。还记录一个数组cnt，表示拿当前位置i更新后，从pos[j]到i的种类数变为多少。

我们可以看出，如果pre[i]<pos[j]，那么当前的i值在j~i-1中没有出现过，所以cnt[j]++；

之后处理时如果发现当前cnt值已经大于pos，需要把pos向后移，知道重新为原来的种类数。

我们只需要记录n^(1/2)个，所以时间复杂度为O(n*n^(1/2));

附上代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int a[40100],qian[40100],hou[40100],n,m,f[40100];int s,pos[40100],cnt[40100];int main(){// freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(qian,-1,sizeof(qian)); memset(f,30,sizeof(f)); s=(int)sqrt(n+0.5); f[0]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=s;j++) if(qian[a[i]]<=pos[j]) cnt[j]++; qian[a[i]]=i; for(int j=1;j<=s;j++) { if(cnt[j]>j) { int now=pos[j]+1; while(qian[a[now]]>now) now++; pos[j]=now; cnt[j]--; } } for(int j=1;j<=s;j++) if(f[pos[j]]+j*j