Codeforces834D - The Bakery
Description
给出一个\(n(n\leq35000)\)个数的数列\(\{a_i\}\)和\(m(m\leq50)\)。将原数列划分成\(m\)个连续的部分,每个部分的权值等于其中不同的数的个数。求所有划分方案中,所有部分权值和中的最大值。
Solution
线段树优化DP。
记录\(f[k][i]\)表示将前\(i\)个数划分为\(k\)段的最大权值和,\(w(i,j)\)表示\([L,R]\)的权值,那么容易列出转移方程:
考虑一下如何简化$w$。记录$a_x$上一次出现的位置为$pre_x$,则$a_x$为$pre_x+1\leq i \leq x$的$w(i,x)$提供了$1$的贡献。那么我们如果想从$w(i,x-1)$转移到$w(i,x)$,只需对区间$[pre_x+1,x]$加$1$即可。
那么我们要做的就是维护$f[k-1][j]+w(j+1,i)$的区间最值,用线段树即可。第二维由$i$变为$i+1$时,对线段树进行一次区间加即可。
> 时间复杂度$O(nk\cdot logn)$。
##Code
```cpp
//The Bakery
#include <cstdio>
inline char gc()
{
static char now[1<<16],*s,*t;
if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}
return *s++;
}
inline int read()
{
int x=0; char ch=gc();
while(ch<'0'||'9'<ch) ch=gc();
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();
return x;
}
inline int max(int x,int y) {return x>y?x:y;}
const int N=4e4;
int n,m,a[N];
int pre[N],pre1[N];
#define Ls (p<<1)
#define Rs (p<<1|1)
const int N1=N<<2;
int rt,val[N1]; int add[N1];
void update(int p) {val[p]=max(val[Ls],val[Rs]);}
void addV(int p,int v) {add[p]+=v,val[p]+=v;}
void pushdw(int p) {if(add[p]) addV(Ls,add[p]),addV(Rs,add[p]),add[p]=0;}
int optL,optR;
void ins(int p,int L0,int R0,int v,int type)
{
if(optL<=L0&&R0<=optR)
{
if(type==1) addV(p,v);
else val[p]=v;
return;
}
pushdw(p);
int mid=L0+R0>>1;
if(optL<=mid) ins(Ls,L0,mid,v,type);
if(mid<optR) ins(Rs,mid+1,R0,v,type);
update(p);
}
int query(int p,int L0,int R0)
{
if(optL<=L0&&R0<=optR) return val[p];
pushdw(p);
int mid=L0+R0>>1; int r=0;
if(optL<=mid) r=max(r,query(Ls,L0,mid));
if(mid<optR) r=max(r,query(Rs,mid+1,R0));
return r;
}
int f[N];
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
pre[i]=pre1[a[i]],pre1[a[i]]=i;
}
rt=1;
for(int k=1;k<=m;k++)
{
for(int i=k;i<=n;i++)
{
optL=pre[i],optR=i-1,ins(rt,0,n,1,1);
optL=0,optR=i-1,f[i]=query(rt,0,n);
}
if(k==m) break;
for(int i=0;i<=n;i++) optL=optR=i,ins(rt,0,n,f[i],2);
}
printf("%d\n",f[n]);
return 0;
}
```\]
最新文章
- jquery-treegrid树状表格的使用(.Net平台)
- 写自己的Socket框架(一)
- struts.xml的编辑
- 用CSS3的transform来做一个立方体
- LUA OOP编程实现方法
- hdu3247Resource Archiver(ac自动机+spfa)
- exp、imp简单测试
- angular : direative : scope | 指令scope里的符号@,=
- python 爬取天猫美的评论数据
- HTML5 Audio/Video 标签,属性,方法,事件汇总 (转)
- 1.4 PCI总线的中断机制
- CSS3 3D立方体效果
- Django组件-Forms组件
- Kafka相关内容总结(存储和性能)
- 面试简单整理之web
- Bootstrap 面板(Panels)
- Asp.Net T4模板生成三层架构
- (三)Hyperledger Fabric 1.1安装部署-chaincode测试
- JS中字符串那些事~
- tf变换(1)