# ECNU 3355 开心消消乐 （dp）

## Examples input

5
1 2 2 1 1


## Examples output

13


## AC 代码

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define per(x, a, b) for (int x = a; x <= b; x++)
#define rep(x, a, b) for (int x = a; x >= b; x--)

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e2 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;
int n, a[maxn];
LL dp[maxn][maxn][maxn];

LL dfs(int l, int r, int x) {
if (dp[l][r][x])
return dp[l][r][x];
if (l == r)
return dp[l][r][x] = (x + 1) * (x + 1);
else if (l < r) {
dp[l][r][x] = dfs(l, r - 1, 0) + (x + 1) * (x + 1);
for (int i = l; i < r; i++) {
if (a[i] == a[r])
dp[l][r][x] =
max(dp[l][r][x], dfs(i + 1, r - 1, 0) + dfs(l, i, x + 1));
}
return dp[l][r][x];
}
return 0;
}
int main() {
#ifdef LOCAL_IM0QIANQIAN
freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
#else
IO;
#endif // LOCAL_IM0QIANQIAN

while (cin >> n) {
mem(dp, 0);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << dfs(0, n - 1, 0) << endl;
}
return 0;
}