[bzoj1587] [Usaco2009 Mar]Cleaning Up 打扫卫生

　　首先（看题解）可得。。。分成的任意一段中的不同颜色个数都<=根号n。。。不然的话直接分成n段会更优= =

　　然后就好做多了。。

　　先预处理出对于每头牛i，和它颜色相同的前一头和后一头牛的位置。

　　假设当前枚举到第i头牛，pos[j]表示第pos[j]头~第i头牛之间颜色种数<=j。num[j]表示第pos[j]头~第i头牛之间具体的颜色种数。

　　每次i增大时，就要把pos数组和num数组更新。对于新加进来的牛i，如果和它颜色相同的前一头牛不在pos[j]~i的范围中，那么就要把num[j]+1。

　　但根据定义，num[j]<=j,所以如果num[j]>j的话就要把pos[j]往i的方向挪。。。如果与第pos[j]头牛颜色相同的后一头牛不在pos[j]~i的范围中，删去第pos[j]头牛后区间里的颜色数量就会-1。。。。

　　DP，设f[i]表示将1~i头牛分成若干段的最小不和谐度。。f[i]=min{f[pos[j]-1]+num[j]^2}，（1<=j<=n^0.5）。。。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #define us unsigned short

 using namespace std;

 const int maxn=;

 us pre[maxn],next[maxn],precol[maxn],nextcol[maxn];

 us a[maxn],b[],c[],f[maxn];//b[j]： b[j]~i中不同数字个数<=j c[j]表示b[j]+1到i出现的不同数字的个数

 us i,j,n,m;

 us ra;char rx;

 inline us read(){

     rx=getchar();ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 int main(){

     n=read();m=read();

     for(i=;i<=m;i++)nextcol[i]=n+;m=floor(sqrt(n));

     for(i=;i<=n;i++)

         a[i]=read(),pre[i]=precol[a[i]],precol[a[i]]=i;

     for(i=n;i;i--)

         next[i]=nextcol[a[i]],nextcol[a[i]]=i;

     for(i=;i<=m;i++)b[i]=;

     for(i=;i<=n;i++)

         for(j=;j<=m;j++){

             if(pre[i]<b[j]){

                 c[j]++;

                 if(c[j]>j){while(next[b[j]]<=i)b[j]++;b[j]++;c[j]--;}

             }

             if(f[b[j]-]+c[j]*c[j]<f[i]||!f[i])f[i]=f[b[j]-]+c[j]*c[j];

         }

     printf("%d\n",f[n]);

     return ;

 }

巴特西

[bzoj1587] [Usaco2009 Mar]Cleaning Up 打扫卫生

最新文章

热门文章