Steven_MengのBlog

传送门

建议先做这道题,有一些套路是一模一样的。

考虑如何$dp$,$dp[i][j]$表示现在扫到第$i$个数,用了$j$段区间,最大的总价值,$cnt(l,r)$表示在区间$[l,r]$中不同的数的个数。

考虑在区间$[1,p]$分段,很容易列出$dp$方程:

其中

容易算出,枚举$i$复杂度为$O(k)$,枚举$p$复杂度为$O(n)$,计算$cnt$复杂度为$O(n)$

总复杂度为$O(n^2k)$,会$TLE$


考虑如何优化,发现复杂度瓶颈在寻找最大值和计算$cnt$,考虑线段树优化。

考虑计算数组$lst[i]$,表示颜色$a[i]$上一次出现的地方,这个$O(n)$ 在输入时预处理即可。

对于$dp$数组每一层,每次跑$dp$都重建一个线段树。

发现枚举到$a[i]$,$[lst[i],i-1]$都要$+1$,因为只有对于区间$[p,i] (p \in [lst[i],i-1])$,$a[i]$才算新出现的元素。

查询时,查询$[0,j-1]$$dp$数组最大值即可。

时间复杂度$O(kn\log n)$

代码里面$dp$数组下标从$0$开始是为了更方便地计算$[0,j-1]$$dp$数组最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#define MAXN 35005
#define MAXM 51
using namespace std;
int dp[MAXM][MAXN];
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace SegmentTree{
struct node{
int l,r;
int maxn,tag;
}tree[MAXN<<2];
#define lc i<<1
#define rc i<<1|1
inline void pushup(int i){
tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
}
inline void pushdown(int i){
if (tree[i].tag){
tree[lc].tag+=tree[i].tag;
tree[lc].maxn+=tree[i].tag;
tree[rc].tag+=tree[i].tag;
tree[rc].maxn+=tree[i].tag;
tree[i].tag=0;
}
}
void Build(int i,int lev,int l,int r){
tree[i].l=l,tree[i].r=r;
tree[i].tag=0;
if (l==r){
tree[i].maxn=dp[lev][l];
return ;
}
int mid=(l+r)>>1;
Build(lc,lev,l,mid);
Build(rc,lev,mid+1,r);
pushup(i);
}
void Update(int i,int L,int R,int val){
if (L<=tree[i].l&&tree[i].r<=R){
tree[i].maxn+=val;
tree[i].tag+=val;
return ;
}
int mid=(tree[i].l+tree[i].r)>>1;
pushdown(i);
if (L<=mid) Update(lc,L,R,val);
if (mid<R) Update(rc,L,R,val);
pushup(i);
}
int Query(int i,int L,int R){
if (L<=tree[i].l&&tree[i].r<=R){
return tree[i].maxn;
}
int mid=(tree[i].l+tree[i].r)>>1,ans=0;
pushdown(i);
if (L<=mid) ans=max(ans,Query(lc,L,R));
if (mid<R) ans=max(ans,Query(rc,L,R));
return ans;
}
}
using namespace SegmentTree;
int lst[MAXN],lstcolor[MAXN];
int a[MAXN];
//lst[i]表示a[i]这种颜色最后出现的位置
//lstcolor[i]表示颜色i最后出现的位置
//类似于一个链表吧。。。
int main(){
int n=read(),k=read();
for (register int i=1;i<=n;++i){
a[i]=read();
lst[i]=lstcolor[a[i]];
lstcolor[a[i]]=i;
}
for (register int i=1;i<=k;++i){
Build(1,i-1,0,n);
for (register int j=1;j<=n;++j){
Update(1,lst[j],j-1,1);
dp[i][j]=Query(1,0,j-1);
}
}
printf("%d\n",dp[k][n]);
}

 评论