「BZOJ1584」[Usaco2009 Mar] Cleaning Up 打扫卫生
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
1
2
1
3
2
2
3
4
3
4
3
1
4
Sample Output
11
题解
不会做T T看了半天题解
这题首先可以发现最差情况是将数列a分成n段，代价为n
那么一定不能有划分出的一段超过√n个
这样一来每次的转移就是在√n个内了f[i]=min{f[b[j]]+j*j}，j<=√n
其中b[j]表示的是从i开始到b[j]+1，共有j个不同的数字
对于b数组的维护，可以随意脑补一下
比如用pre[a[i]]记录a[i]上次出现的位置，c[j]记录b[j]+1到i的不同数字个数
这样每次i++时，先更新c数组，即如果pre[a[i]]<=b[i]，那就无视，不然c[j]++
如果c[j]++了，那么就要从b[i]+1开始找一个只在b[j]+1到i出现一次的，删到它为止
复杂度好像应该是n√n了吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[40005],f[40005]; int b[205],cnt[205]; int pre[40005]; int main() { memset(f,127/3,sizeof(f)); memset(pre,-1,sizeof(pre)); n=read();m=read(); int tot=0; for(int i=1;i<=n;i++) { int x=read(); if(x!=a[tot])a[++tot]=x; } n=tot; m=trunc(sqrt(n)); f[0]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) if(pre[a[i]]<=b[j])cnt[j]++; pre[a[i]]=i; for(int j=1;j<=m;j++) if(cnt[j]>j) { int t=b[j]+1; while(pre[a[t]]>t)t++; b[j]=t;cnt[j]--; } for(int j=1;j<=m;j++) f[i]=min(f[i],f[b[j]]+j*j); } printf("%d",f[n]); return 0; } |
计数器 9865067
OI 课件=>
OI 课件=>
上面题解写错了吧
“其中b[j]表示的是从i开始到b[j]+1，共有j个不同的数字”
应该是
“其中b[j]表示的是从b[j]+1开始到i，共有j个不同的数字”