ZYB的画图计划

题目

题目描述
在20202020年22月1414日这一天，ZYBZYB终于找到了自己的妹子，可喜可贺可喜可贺。

找到妹子之后，ZYBZYB想做的第一件事情是给他的妹子画一幅世界名画。这副画的长为NN,宽为11(清明上河图，ZYBZYB打算用MM种颜色来画这幅画，为了方便，他将这副画抽象成了NN个1×11×1的格子，每一个格子需要被涂成颜色cici.ZYBZYB有一支画笔，可以随时变换成任何颜色，但是这支画笔在变换出一种颜色之后，之后就再也不能变换出这种颜色了(也就是说，每种颜色只能用一次)。每一次,ZYBZYB可以选择连续的一段格子并将这段格子的颜色都涂成画笔上的颜色，如果之前有颜色则会覆盖之前的颜色。一开始所有的格子都是无色的。每涂一个格子就需要花费1单位的时间。

为了彰显出自己的努力，ZYBZYB希望能够使得自己完成作品的时间尽量长。同时他可以自由调整选择颜色的顺序。你能帮帮他求出这个最长时间吗/p>

输入格式
一行两个整数n,mn,m.

第二行NN个正整数cici,描述这张图的颜色序列。

输出格式
一行输出最大值。

样例1
输入

5 2
1 1 2 2 3
输出

11
解释

有66种不同的颜色序列:

1 2 3:1先涂(1,5),2涂(3,5),3涂(5,5) 花费9单位时间。当然,1涂(1,2),2涂(3,4),3涂(5,5)也是合法解，但花费时间很少。

1 3 2:1先涂(1,5),3涂(3,5),2涂(3,4) 花费10单位时间

2 1 3:2先涂(1,5),1只能涂(1,2),3只能涂(5,5) 花费8单位时间

2 3 1:2先涂(1,5),3涂(5,5),1涂(1,2)花费8单位时间

3 1 2:3先涂(1,5),1涂(1,4),2涂(3,4)花费11单位时间

3 2 1:3先涂(1,5),2涂(1,4),1涂(1,2)花费11单位时间

样例2
输入

5 2
1 2 3 2 1
输出

9
数据范围
对于20%20%的数据,M≤8M≤8
对于40%40%的数据,M≤100M≤100
在所有数据中均匀分布着50%50%的数据,cici是不降的

对于100%100%的数据,N≤100000,M≤5000,1≤ci≤MN≤100000,M≤5000,1≤ci≤M.数据保证所有颜色至少出现一次，同时存在一种合法画法能够画出这张图。

思路

暴力：
暴力枚举颜色的先后顺序,对于每种颜色，他能够涂的范围 是自己的从最左到最右，而如果中间有一个格子被之前的颜 色涂过且正好颜色相同，则这种方法无解。而其真正可以涂 的一段是包含自己的没有被固定颜色的最长连续段，判断一 下即可。时间复杂度O(M! * N)

正解：
若每种段只出现一次，可以注意到我们每涂完一种颜色，就 将整个序列分为两段，所以，我们不妨令fi,j表示涂完第i种 颜色到第j种颜色，最多可以涂多少。那么我们 有dpl,r = maxl≤k≤rdpl,k 1 + dpk+1,r + costi,j，注意到该式 虽然与四边形不等式稍有区别，但通过一样的不等式分析仍 然可以得到dpi,j + dpi+1,j+1 ≥ dpi,j+1 + dpi + 1, j,故上式可 以直接用四边形不等式优化。

代码

来源：LK自动机