bzoj1584--DP，bzoj1584

bzoj1584--DP，bzoj1584

題目大意：
有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 }