bzoj1584--DP

2017-01-04 08:19:45来源:cnblogs.com作者:gjghfd人点击

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

 

思路:
显然如果连续的一段数字相同,我们可以把它们合并成一个数字。

用f[i]表示在1~i这一段的最小不河蟹度。因为答案最大为n,显然不可能出现一段中有超过sqrt(n)个不同的数。

定义b[j],使b[j]+1~i中不同的数的个数等于j且b[j]最小,那么可以得到:f[i]=min{f[j]+j*j},j<=sqrt(n)

怎么求b[j]呢?定义p[k]表示值为k的数前一次出现的位置、c[j]表示b[j]+1~i中有多少个不同的数。

枚举i,更新p,c,对于b[j],若c[j]>j,则需要将b[j]增大,直到a[b[j]]在b[j]+1~i中不出现,一个while即可。

时间复杂度O(n*sqrt(n))

 

代码:

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 char buf[10000000],*p1=buf; 7 inline void Read(int& x){ 8     char c=*p1++; 9     for(;c<'0'||c>'9';c=*p1++);10     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=*p1++);11 }12 int i,j,k,n,m,x,a[40001],c[40001],f[40001],Last,Pre,p[40001],b[201],Num;13 bool B[201];14 int main()15 {16     fread(buf,1,10000000,stdin);17     Read(n);Read(m);18     for(i=1;i<=n;i++){19         Read(x);20         if(x!=a[Num])a[++Num]=x;21     }22     n=Num;m=sqrt((double)n);23     memset(f,127,sizeof(f));24     for(i=1,f[0]=0;i<=n;i++){25         for(j=1;j<=m;j++)if(p[a[i]]<=b[j])c[j]++;26         for(j=1,p[a[i]]=i;j<=m;j++)27         if(c[j]>j){28             k=b[j]+1;29             while(p[a[k]]!=k)k++;30             b[j]=k;c[j]--;31         }32         for(j=1;j<=m;j++)33         if(f[b[j]]+j*j<f[i])f[i]=f[b[j]]+j*j;34     }35     printf("%d",f[n]);36     return 0;37 }
bzoj1584

 

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台