hdu5009
1390 ワード
構想:i位に対して、その前のx位を探し出して、x+1からi位にj種の色を含むようにし、同時にj*jどのように急速にiの前の異なる色を探して、私はここでlとrの2つの配列を使って、差は多くなくて最後に現れた異なる色の間をつなぎ合わせて、簡単に前の異なる色を見つけることができます.
#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
",dp[m]);
}
return 0;
}