学步园

思路：对于第i位，找出在它之前的第x位，使得第x+1到第i位中包括j种颜色，同时j*j<i，那么可以dp[i]=min(dp[x]+j*j,dp[i])

如何快速找i之前的不同颜色，我这里用了l和r两个数组，差不多是将最后出现的不同颜色之间连起来，就可以轻松找到前一个不同颜色了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int n,m,a[50005],dp[50005],c,l[50005],r[50005],p[50005];
int num;
map<int,int>mp;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        m=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&c);
            if(i==0)a[++m]=c;
            else if(c!=a[m])a[++m]=c;
        }
        for(int i=0;i<=m;i++)dp[i]=i;
        r[0]=1;
        num=0;
        mp.clear();
        for(int i=1;i<=m;i++)
        {
            if(!mp[a[i]])mp[a[i]]=++num;
            else
            {
                int temp=p[mp[a[i]]];
                r[l[temp]]=r[temp];
                l[r[temp]]=l[temp];
            }
            r[i]=i+1;
            l[i]=i-1;
            p[mp[a[i]]]=i;
            int cnt=0;
            for(int j=l[i];;j=l[j])
            {
                cnt++;
                dp[i]=min(dp[i],dp[j]+cnt*cnt);
                if(j==0||cnt*cnt>i)break;
            }
        }
        printf("%d\n",dp[m]);
    }
    return 0;
}