记录编号	602647	评测结果	AAAAAAAAAA
题目名称	2034.[Tyvj]方块消除	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	0.177 s
提交时间	2025-07-05 13:25:27	内存使用	15.77 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int N=205;
int f[N][N][N],n,m,c[N],vis[N],sum[N][N],L[N],R[N];
int pw(int x){return x*x;}
int main(){
	freopen("eliminate.in","r",stdin);
	freopen("eliminate.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",c+i);
		m=max(m,c[i]);
		vis[c[i]]=1;
	}
	for(int i=1;i<=m;i++){
		if(!vis[i])continue;
		for(int j=1;j<=n;j++){
			sum[i][j]=sum[i][j-1]+(c[j]==i);
		}
	}
	for(int i=1;i<=n;i++){
		f[i][i][0]=1;
		for(int j=1;j<=m;j++){
			if(!vis[j]||j==c[i])continue;
			f[i][i][j]=1;
		}
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n;i++){
			int j=i+len-1;if(j>n)break;
			for(int k=1;k<=m;k++)L[i]=R[i]=0;
			for(int k=j;k>=i;k--)L[c[k]]=k;
			for(int k=i;k<=j;k++)R[c[k]]=k;
			for(int k=1;k<=m;k++){
				if(!(sum[k][j]-sum[k][i-1]))continue;
				if(c[i]==k&&c[j]==k)f[i][j][k]=f[i+1][j-1][k];
				else if(c[i]==k)f[i][j][k]=f[i+1][j][k];
				else if(c[j]==k)f[i][j][k]=f[i][j-1][k];
				else f[i][j][k]=f[L[k]][R[k]][k]+f[i][L[k]-1][0]+f[R[k]+1][j][0];
			}
			for(int k=1;k<=m;k++){
				if(!(sum[k][j]-sum[k][i-1]))continue;
				f[i][j][0]=max(f[i][j][0],f[i][j][k]+pw(sum[k][j]-sum[k][i-1])); 
			}
			for(int k=1;k<=m;k++)if(!(sum[k][j]-sum[k][i-1]))f[i][j][k]=f[i][j][0];
		}
	}
	printf("%d\n",f[1][n][0]);
	return 0;
}