Description：

一行 $n$ 个格子，每次可以给连续的一些格子刷同一种颜色，要求刷 $m$ 次，每次刷一种不同的颜色，给出最后的状态，最大化刷的总长度。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 5000$

Solution：

既然保证有解，那么两个相同颜色的格子之间的格子一定是和外界无关的，那么我们可以建出一个类似树的结构，每次把并列的都设成某个节点的子树，由于 $m\leqslant 5000$ 所以可以支持 $O(m^2)$ 的做法，我们每次把一个点所有的在一个块内的子节点都拿出来，他们之间是可以交叉的，并且它们之间没有相对顺序，然后我们给他们做一个 $O(m^2)$ 的区间 $DP$ ，因为由于把一个整个的区间分成两个互不相关的部分一定不优，所以我们只要考虑每次在两边哪一侧插入到整个序列的最底部就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int col[MAXN];

#define MAXM 5010

int lef[MAXM],rig[MAXM];

vector<int> son[MAXM];

int fa[MAXM];

int nxt[MAXN],last[MAXM];

bool cmp_pos(int a,int b){return lef[a] < lef[b];}

int c[MAXM];

int f[MAXM][MAXM];

int solve()

{

	for(int l = 1;l <= c[0];++l)

	{

		for(int i = 1;i <= c[0] - l + 1;++i)

		{

			int j = i + l - 1;

			f[i][j] = max(f[i][j - 1],f[i + 1][j]) + rig[c[j]] - lef[c[i]] + 1;

		}

	}

	return f[1][c[0]];

}

int dp(int k)

{

	int ans = 0;

	sort(son[k].begin(),son[k].end(),cmp_pos);

	for(int i = 0;i < son[k].size();++i)ans += dp(son[k][i]);

	vector<int>::iterator it = son[k].begin();

	for(int l = lef[k],r;l < rig[k];l = r)

	{

		r = nxt[l];

		c[0] = 0;

		while(it != son[k].end() && rig[*it] < r)

		{

			c[++c[0]] = *it;

			++it;

		}

		ans += solve();

	}

	return ans;

}

int main()

{

	//freopen("kkk1.in","r",stdin);

	//freopen("kkk1.out","w",stdout);

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

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

	{

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

	}

	memset(lef,0x3f,sizeof(lef));

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

	{

		lef[col[i]] = min(lef[col[i]],i);

		rig[col[i]] = max(rig[col[i]],i);

	}

	for(int i = 1;i <= m;++i)for(int j = 1;j <= m;++j)

		if(lef[i] < lef[j] && rig[i] > rig[j])

			if(fa[j] == 0 || rig[i] - lef[i] < rig[fa[j]] - lef[fa[j]])fa[j] = i;

	for(int i = 1;i <= m;++i)son[fa[i]].push_back(i);

	for(int i = 0;i <= m;++i)last[i] = n + 1;

	for(int i = n;i >= 0;--i)

	{

		nxt[i] = last[col[i]];last[col[i]] = i;

	}

	lef[0] = 0;rig[0] = n + 1;

	cout << dp(0) << endl;

	return 0;

}