CF833B The Bakery

CF, DP, 线段树

　　题意：把n个数分成k个区间，每个区间的价值为区间内不同数字的个数，问价值和最大为多少。 - 原题链接

　　神奇的线段树… 先碰到多校那场dirt ratio再来做的这道DP，原来这已经是个常（不）规（会）套路了😕。

　　首先，我们用f[i][j]表示前j个数分成i个区间的最大价值和，则有转移方程：

　　显然，如果用暴力方法转移，复杂度为O(kn^2)，所以这里我们利用线段树来维护value。

　　用辅助数组pos[a[j]]表示a[j]最后一次出现的位置，pre[j]表示a[j]上一次出现位置的下一位。在前i-1个区间已经求出的情况下，我们考虑第i层，假设当前枚举到a[j]，如果从pre[j]到j这段区间任选一个起点x，则[x, j]这段区间都只会有一个a[j]。我们用数组p[y]表示以p[y]为左端点的区间的不同数的个数，那么a[j]的贡献就是令p[pre[j]~j]区间整体+1。若将数组p[y]初始为f[i-1][y-1]，则p[y]最终表示的就是f[i-1][y-1]+value[y, j]，转移时只需要查询p[1~j]的最大值，复杂度优化到O(nklogn)。 


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
95
96
97
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define kl (k<<1)
#define kr ((k<<1)+1)
#define mid ((l+r)>>1)
using namespace std;
const int maxn=35000+10, N=50+10;
int n, k, a[maxn], f[N][maxn];
int pre[maxn], pos[maxn];
struct node
{
	int ret, flag;
}tr[maxn<<2];
void Push_down(int k)
{
	tr[kl].ret+=tr[k].flag, tr[kl].flag+=tr[k].flag;
	tr[kr].ret+=tr[k].flag, tr[kr].flag+=tr[k].flag;
	tr[k].flag=0;
	return ;
}
void Push_up(int k)
{
	tr[k].ret=max(tr[kl].ret, tr[kr].ret);
	return ;
}
void Build(int x, int k=1, int l=1, int r=n)
{
	tr[k].flag=0;
	if(l==r)
	{
		tr[k].ret=f[x][l-1];	//注意是l-1
		return ;
	}
	Build(x, kl, l, mid);
	Build(x, kr, mid+1, r);
	Push_up(k);
	return ;
}
void Update(int ll, int rr, int k=1, int l=1, int r=n)
{
	if(rr< l || r <ll)	return ;
	if(ll<=l && r<=rr)
	{
		tr[k].ret++, tr[k].flag++;
		return ;
	}
	Push_down(k);
	Update(ll, rr, kl, l, mid);
	Update(ll, rr, kr, mid+1, r);
	Push_up(k);
	return ;
}
int Query(int ll, int rr, int k=1, int l=1, int r=n)
{
	if(rr< l || r <ll)	return 0;
	if(ll<=l && r<=rr)	return tr[k].ret;
	int tl=Query(ll, rr, kl, l, mid), tr=Query(ll, rr, kr, mid+1, r);
	Push_up(k);
	return max(tl, tr);
}
int main()
{
	while(scanf("%d%d", &n, &k)!=EOF)
	{
		memset(pre, 0, sizeof pre);
		memset(pos, 0, sizeof pos);
		for(int i=1; i<=n; i++)
		{
			scanf("%d", &a[i]);
			pre[i]=pos[a[i]]+1;
			pos[a[i]]=i;
		}
		for(int i=1; i<=k; i++)
		{
			Build(i-1);
			for(int j=1; j<=n; j++)
			{
				Update(pre[j], j);
				f[i][j]=Query(1, j);
			}
		}
		printf("%d\n", f[k][n]);
	}
	return 0;
}