Description

有N头奶牛,每头那牛都有贰个标注Pi,1 <= Pi <= M <= N <=
50000。未来Farmer John要把这一个奶牛分成若干段,定义每段的不河蟹度为:

若那段里有k个不一样的数,那不河蟹度为k*k。那总的不河蟹度就是负有段的不河蟹度的总数。

bzoj1584–DP,bzoj1584

难点大意:
有N头奶牛,每头这牛都有八个标注Pi,1 <= Pi <= M <= N <=
四千0。未来Farmer
John要把这个奶牛分成若干段,定义每段的不河蟹度为:若那段里有k个差别的数,那不河蟹度为k*k。那总的不河蟹度正是具有段的不河蟹度的总额。

 

思路:
大廷广众即使一而再的一段数字同样,我们得以把它们统10%二个数字。

用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的数前3次面世的职责、c[j]表示b[j]+1~i中有微微个不相同的数。

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

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

 

代码:

图片 1

 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

 

http://www.bkjia.com/cjjc/1184857.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1184857.htmlTechArticlebzoj1584–DP,bzoj1584 标题马虎:
有N头奶牛,每头这牛都有1个标注Pi,1 = Pi = M = N = 五千0。未来Farmer
John要把那个奶牛分成若干段,定义每段的…

Input

先是行:多个整数N,M

第3..N+1行:N个整数代表每一个奶牛的数码

Output

3个整数,代表最小不河蟹度

Sample Input

13 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]表示的是从b[j]+1伊始到i,共有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出现1遍的,删到它甘休

复杂度好像应该是n√n了吧

 

对于拥有,下限至少是n是足以鲜明的,因为每一种独立一段,即可。

还有那几个m是没有啥样用的,那么小编得以想假诺一段的差异个数已经超先生过√n

那正是说其消费已经为n是没有意思的,但是此地的√n,是向下取整的所以照旧**

有意义的,能够取到

由此只要求记录差异的√n的变换即可,那么哪些保护,**

**是根号n维护对啊,然后也是根号n转移即可,很好想的。**

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 
 7 #define N 207
 8 #define M 40007
 9 using namespace std;
10 inline int read()
11 {
12     int x=0,f=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 
18 int n,m;
19 int a[M],f[M];
20 int b[N],cnt[N];
21 int pre[M];
22 
23 int main()
24 {
25     memset(f,127/3,sizeof(f));
26     memset(pre,-1,sizeof(pre));
27     n=read();m=read();
28     int tot=0;
29     for(int i=1;i<=n;i++)
30     {
31         int x=read();
32         if(x!=a[tot])a[++tot]=x;
33     }
34     n=tot;
35     m=trunc(sqrt(n));
36     f[0]=0;
37     for(int i=1;i<=n;i++)
38     {
39         for(int j=1;j<=m;j++)
40             if(pre[a[i]]<=b[j])cnt[j]++;
41         pre[a[i]]=i;
42         for(int j=1;j<=m;j++)
43             if(cnt[j]>j)
44             {
45                 int t=b[j]+1;
46                 while(pre[a[t]]>t)t++;
47                 b[j]=t;cnt[j]--;
48             }
49         for(int j=1;j<=m;j++)
50             f[i]=min(f[i],f[b[j]]+j*j);
51     }
52     printf("%d",f[n]);
53 }

 

相关文章