1584: [Usaco2009 Mar]Cleaning Up 打扫卫生
- Time Limit: 10 Sec Memory Limit: 64 MB
- Submit: 677 Solved: 481
- [Submit][Status][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=1584 ]
- 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
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)
- #include<bits/stdc++.h>
- using namespace std;
- int const N=40000+10;
- int const inf=1e8;
- int dp[N],n,m,b[210],pre[N],c[N],t[N];
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++){
- scanf("%d",&c[i]);
- pre[i]=t[c[i]];
- t[c[i]]=i;
- }
- memset(t,0,sizeof(t));
- int num=0;
- for(int i=1;i<=n;i++){
- int k=0;
- for(int j=num;j>=1;j--)
- if(b[j]>pre[i]) {
- k=j; break;
- }
- if(k){
- for(int j=k-1;j>=1;j--)
- b[j+1]=b[j];
- b[1]=i;
- }
- if(num<200 && !t[c[i]]) b[++num]=1;
- dp[i]=inf;
- for(int j=1;j<=num;j++)
- dp[i]=min(dp[i],dp[b[j]-1]+j*j);
- }
- cout<<dp[n]<<endl;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3113783.html