记录编号	602696	评测结果	AAAAAAAAAA
题目名称	2034.[Tyvj]方块消除	最终得分	100
用户昵称	OTTF	是否通过	通过
代码语言	C++	运行时间	1.114 s
提交时间	2025-07-05 15:06:23	内存使用	11.27 MiB

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

constexpr int N = 233;

int n;
int nums[N];
int m;
int col[N];
int cc[N];
long long dp[N][N][N];

int main () {
	
	freopen ("eliminate.in" ,"r", stdin);
	freopen ("eliminate.out", "w", stdout);
	
	cin >> n;

	if (n == 0) {
		cout << 0 << endl;
		return 0;
	}

	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
	}

	for (int i = 1; i <= n; i++) {
		if (nums[i] != nums[i - 1]) {
			m++;
			col[m] = nums[i];
		}
		cc[m]++;
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			dp[i][i][j] = (cc[i] + j) * (cc[i] + j);
		}
	}

	for (int len = 1; len <= m; len++) {
		for (int i = 1, j = i + len - 1; j <= m; i++, j++) {
			for (int k = 0; k <= n; k++) {
				dp[i][j][k] = dp[i][j - 1][0] + (cc[j] + k) * (cc[j] + k);
				for (int l = i; l < j; l++) {
					if (col[l] == col[j]) {
						dp[i][j][k] = max (dp[i][j][k], dp[i][l][cc[j] + k] + dp[l + 1][j - 1][0]);
					}
				}
			}
		}
	}

	cout << dp[1][m][0] << endl;

	return 0;
}