C++(g++ 7.5.0) 解法, 执行用时: 61ms, 内存消耗: 3624K, 提交时间: 2022-11-23 10:06:40

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int dp[N],a[N],last[N],ne[N],la[N];
map<int,int> m;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int len;
    cin>>len;
    dp[0]=0;
    memset(dp,0x3f,sizeof dp);
    for(int i=1,j=0;i<=len;i++){
        cin>>a[i];
        m[a[i]]++;
    }
    int idx=0;
    dp[0]=0;
    memset(dp,0x3f,sizeof dp);
    int ma=300;
    for(auto &[i,j]:m) j=++idx;
    for(int i=1;i<=len;i++){
        a[i]=m[a[i]];
        last[i]=i-1;
        ne[i]=i+1;
    }
    dp[0]=0;
    last[0]=-1;
    for(int i=1;i<=len;i++){
        if(la[a[i]]){
            int j=la[a[i]];
            last[ne[j]]=last[j];
            ne[last[j]]=ne[j];
        }
        la[a[i]]=i;
        int cnt=0;
        for(int j=last[i];~j&&cnt<ma;j=last[j]){
            cnt++;
            dp[i]=min(dp[i],dp[j]+cnt*cnt);
        }
    }
    cout<<dp[len];
}

C++(clang++ 11.0.1) 解法, 执行用时: 41ms, 内存消耗: 3808K, 提交时间: 2022-10-06 15:42:26

#include<bits/stdc++.h>
#define qq 50005
using namespace std;
long long f[qq],a[qq],nxt[qq],pre[qq],sum=0,n,tmp;
unordered_map<long long,long long>vis;
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n;
    tmp=sqrt(n);
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=0;i<=n;++i)pre[i]=i-1,nxt[i]=i+1;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
	for(int i=1;i<=n;i=nxt[i]){
    	if(vis[a[i]]){
			int j=vis[a[i]];
			nxt[pre[j]]=nxt[j],pre[nxt[j]]=pre[j];
		}
    	vis[a[i]]=i,sum=0;
    	for(int j=pre[i];j>=0;j=pre[j]){
    		++sum,f[i]=min(f[i],f[j]+sum*sum);
    		if(sum*sum>i) break;
    	}
    }
    cout<<f[n];
    return 0;
}