Description:

将一个长为 $N$ 的序列划分成 $K$ 段，最大化各段中不同种的数字个数的和。

$1\le N\le 35000$ $1\le K\le min(N,50)$

Solution:

$f[i][j]$ 表示前 $j$ 个数分成 $i$ 段， $DP$ 方程为： $f[i][j]=max(f[i-1][k]+cnt[k+1][j])$ ，转移是 $O(N^3)$ 的，用线段树维护 $f$ 数组，即线段树第 $i$ 个位置表示 $f[cur][i]+cnt[i+1][now]$ ，一个一个的加数，对于新加进来的一个数 $a_i$ ，它只会对 $cnt[pre[a_i]+1][now]$ ~ $cnt[now][now]$ 造成加一的影响，也就只会对 $f[pre[a_i]+1]$ ~ $f[i]$ 造成加一的影响，用线段树区间加实现，每次查询 $[0,now-1]$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 35010

#define MAXK 55

int a[MAXN],pre[MAXN],last[MAXN];

int f[MAXK][MAXN];

struct node

{

	int lc,rc,tag,f;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void pushup(int rt)

{

	t[rt].f = max(t[t[rt].lc].f,t[t[rt].rc].f);

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag == 0)return;

	t[t[rt].lc].tag += t[rt].tag;

	t[t[rt].rc].tag += t[rt].tag;

	t[t[rt].lc].f += t[rt].tag;

	t[t[rt].rc].f += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void build(int &rt,int l,int r,int cur)

{

	rt = newnode();

	t[rt].tag = 0;

	if(l == r)

	{

		t[rt].f = f[cur][l];

		t[rt].lc = t[rt].rc = 0;

		return;

	}

	int mid = ((l + r) >> 1);

	build(t[rt].lc,l,mid,cur);

	build(t[rt].rc,mid + 1,r,cur);

	pushup(rt);

	return;

}

void init()

{

	memset(t,0,sizeof(t));

	ptr = 0;

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt].f;

	}

	pushdown(rt);

	int mid = ((l + r) >> 1);

	int res = 0;

	if(L <= mid)res = max(res,query(t[rt].lc,L,R,l,mid));

	if(R >= mid + 1)res = max(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

void add(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].f += 1;

		t[rt].tag += 1;

		return;

	}

	pushdown(rt);

	int mid = ((l + r) >> 1);

	if(L <= mid)add(t[rt].lc,L,R,l,mid);

	if(R >= mid + 1)add(t[rt].rc,L,R,mid + 1,r);

	pushup(rt);

	return;

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		pre[i] = last[a[i]];

		last[a[i]] = i;

	}

	memset(f,0,sizeof(f));

	for(int i = 1;i <= k;++i)

	{

		init();

		build(root,0,n - 1,i - 1);

		for(int j = 1;j <= n;++j)

		{

			add(root,pre[j],j - 1,0,n - 1);

			f[i][j] = query(root,0,j - 1,0,n - 1);

		}

	}

	cout << f[k][n] << endl;

	return 0;

}