Dicripntion

Lee has a string of n pearls. In the beginning, all the pearls have no color. He plans to color the pearls to make it more fascinating. He drew his ideal pattern of the string on a paper and asks for your help.

In each operation, he selects some continuous pearls and all these pearls will be painted to their target colors. When he paints a string which has k different target colors, Lee will cost k ² points.

Now, Lee wants to cost as few as possible to get his ideal string. You should tell him the minimal cost.

3

1 3 3

10

3 4 2 4 4 2 4 3 2 2

2

7

设f[i]为以i结尾的前i个数划分的序列的最小值，不难得到递推式：
f[i]=min{f[j]+cost(j+1,i)}。

朴素的话复杂度是O(N^2)，过不了，要考虑优化。

然后发现其实答案有一个上界N，因为一个一个消总能做到N划分整个序列。
又因为cost是颜色数的平方，所以当i固定的时候，cost(j+1,i)最多只有sqrt(N)
个取值，要不然肯定不是最优解。

而当cost(j+1,i)一定的时候j一定是越小越好，因为f函数肯定是单调不降的(考虑反证法)。

所以我们只需要找出i一定的时候，对应的最多sqrt(N)个j的位置就行了。

但其实并不是很好求。。。。。

考虑从i-1的sqrt(N)个j来递推i的。
当i的颜色没有在i-1的j中出现的时候，显然只需要取i-1的最近的sqrt(N)-1个j再加上i作为最后一个j。
设k为i-1的第二远的j，那么a[k-1]就是最远出现的颜色，把它还原即可；

而如果出现过的话，颜色集合是不变的，唯有某一个位置换成了i。
记以i-1为右端点的时候a[i]第一次出现的位置是k，那么i-1集合中某个j肯定为k+1，
把这个j换成i就行了。
至于原因？？
因为没有a[i]的时候扫到k时颜色数会+1，所以j变成了一个左端点；
而有a[i]的时候扫到k时颜色数就不会变了。。。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#define pb push_back

#define ll long long

#define maxn 100005

using namespace std;

//g[i][j]表示右端点为i的有j+1个颜色的块的可能的最左端

vector<int> g[maxn];

using namespace std;

const int inf=<<;

int n,a[maxn],f[maxn],b[maxn],ky;

bool v[maxn];

int main(){

    while(scanf("%d",&n)==){

        memset(v,,sizeof(v));

        for(int i=;i<=n;i++) g[i].clear();

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

            scanf("%d",a+i);

            //先把重复的去了，没有用

            if(a[i]==a[i-]) i--,n--;

        }

        //离散化一下，不然会出事

        for(int i=;i<=n;i++) b[i]=a[i];

        sort(b+,b+n+);

        ky=unique(b+,b+n+)-b-;

        for(int i=;i<=n;i++) a[i]=lower_bound(b+,b+ky+,a[i])-b;

        //颜色数上界，超过上界的cost肯定不在最优解中

        int tp=sqrt(n);

        g[].pb(),v[a[]]=;

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

            if(v[a[i]]){

                /*

                  如果当前颜色在前sqrt(n)种之内，

                  那么第一种的最左端肯定是i，

                  第二种往后的可以根据i-1的递推，

                */

                g[i].pb(i);

                int oo=g[i-].size()-;

                for(int j=;j<=oo;j++){

                    if(a[g[i-][j]-]==a[i]) continue;

                    g[i].pb(g[i-][j]);

                }

            }

            else{

                /*

                  不在之内的话，就得新加进去然后

                  把上一个的最末尾的颜色消除

                */

                v[a[i]]=,g[i].pb(i);

                int m=min((int)g[i-].size(),tp-);

                for(int j=;j<=m;j++) g[i].pb(g[i-][j-]);

                if(m<g[i-].size()){

                    v[a[g[i][m]-]]=;

                }

            }

            /*

            printf("%d:%d\n",i,g[i].size());

            for(int j=0;j<g[i].size();j++) printf("%d ",g[i][j]);

            puts("");

            */

        }

        f[]=;

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

            int cost=,sz=g[i].size()-;

            f[i]=inf;

            for(int j=;j<=sz;j++){

                cost++;

                if(cost*cost>f[i]) continue;

                f[i]=min(f[i],f[g[i][j]-]+cost*cost);

            }

        }

        printf("%d\n",f[n]);

    }

    return ;

}