bzoj 1584-布布扣-bubuko.com

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

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 677 Solved: 481
[Submit][Status][Discuss]

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

f[i]表示到第i个位置的最优解，那么暴力转移f[i]是n^3的，用数据结构维护区间颜色可以做到n^2*log2(n)，但都无法通过此题。
显然每个数独自一段可以做到的答案就是n，由于费用是k^2，那么假如某一段包含了超过n^(0.5)的不同颜色，必然是劣于最优解的。
我们考虑维护一个B数组：
对于每个位置i，都有B[k]表示从i出发向左走，经过颜色不超过k能走的最远距离，也就是最小化每个B[k]
对于一个位置i，找到前一个相同颜色next[i]。
所有小于等于next[i]的B[k]肯定意义不变。
如果存在大于next[i]的B[k]，那么把它们全部后移一位，然后在B[1]插入i；
如果不存在这样的B[k]，那说明加入这个颜色并不会对B数组产生影响。
对于每个位置i，f[i]=min(f[b[k]-1]+k^2)
根据之前的结论，我们只要维护B数组长度不超过n^(0.5)的部分就能得出最优解了。
按照顺序考虑每个位置i，这样无论是转移f数组还是维护B自身，都可以在n^(0.5)时间内完成，总复杂度n*n^(0.5)

 1 #include<bits/stdc++.h>
 2 using namespace std; 
 3 int const N=40000+10;  
 4 int const inf=1e8;  
 5 int dp[N],n,m,b[210],pre[N],c[N],t[N];  
 6 int main(){
 7     scanf("%d%d",&n,&m); 
 8     for(int i=1;i<=n;i++){
 9         scanf("%d",&c[i]);  
10         pre[i]=t[c[i]]; 
11         t[c[i]]=i;  
12     }
13     memset(t,0,sizeof(t));  
14     int num=0;  
15     for(int i=1;i<=n;i++){
16         int k=0;   
17         for(int j=num;j>=1;j--) 
18             if(b[j]>pre[i]) {
19                 k=j; break;  
20             } 
21         if(k){
22             for(int j=k-1;j>=1;j--) 
23                 b[j+1]=b[j];  
24             b[1]=i;
25         }   
26         if(num<200 && !t[c[i]]) b[++num]=1; 
27         dp[i]=inf;  
28         for(int j=1;j<=num;j++)   
29             dp[i]=min(dp[i],dp[b[j]-1]+j*j);  
30     }
31     cout<<dp[n]<<endl; 
32     return 0; 
33 
34 }

View Code

bzoj 1584

原文：https://www.cnblogs.com/ZJXXCN/p/11137136.html