剪贴板 - j6ny75k4

#include <bits/stdc++.h>
using namespace std;
int n, dp[510][510];
int a[510], num[510], cnt, x[510];
signed main() {
	memset(dp, 0x3f, sizeof(dp));
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (i > 1 && a[i] == a[i - 1]) {
			num[cnt]++;
		} else {
			x[++cnt] = a[i];
			num[cnt] = 1;
		}
	}
	for (int i = 1; i <= cnt; i++) {
		if (num[i] >= 2) dp[i][i] = 1;
		else dp[i][i] = 1e9;
	}
	for (int len = 2; len <= cnt; len++) {
		for (int i = 1; i + len - 1 <= cnt; i++) {
			int j = i + len - 1;
			for (int k = i; k < j; k++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
			if (x[i] == x[j]) {
				dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + (num[i] + num[j] <= 2)); 
			}
		}
	}
	if (dp[1][cnt]<1e9) printf("%d", dp[1][cnt]);
	else printf("-1");
	return 0;
}