ECNU 3355 开心消消乐（dp）

Description

大家都玩过一种叫作开心消消乐的游戏。

规则很简单：刚开始有一列不同颜色的方块，每次可以消掉相邻的、颜色相同的若干个（$k$ 个），并获得 $k^2$ 分。现在给出一个游戏的起始局面，问最多能获得多少分？

Input

第一行给出一个整数 $n$ $(1 \le n \le 100)$，表示起始的方块数。

第二行 $n$ 个整数 $a_1,a_2,…,a_n$ $(1 \le a_i \le n)$，用空格隔开，依次表示这列方块的颜色。

Output

输出最多得分。

Examples input

5
1 2 2 1 1

Examples output

思路

记忆化搜索，我们定义 $dp[l][r][x]$ 代表在区间 $[l,r]$，且 $r$ 右侧拥有 $x$ 个与右端点颜色相同的点的情况下所能得到的最优解。

那么假若 $l=r$，显然此时的答案是 $(x+1)^2$，因为后面 $x$ 个点可以和当前这一个点连在一起进行消去操作。

假若 $l

直接消去右端点，此时区间被拆分为 $[l,r-1]$ 与 $[r,r]$，显然这种操作所得到的权值为 $dp[l][r-1][0] + (x+1)^2$

消去中间的某部分，假设我们有一个分割点 $i$，且 $i$ 与 $r$ 点的颜色相同，那么我们可以将区间拆分为 $[l,i]$ $[i+1,r-1]$ $[r,r]$ 三部分，然后先消去 $[i+1, r-1]$，再消去 $[l, i] \cup [r,r]$，这种操作所得到的权值为 $dp[i+1][r-1][0]+dp[l][i][x+1]$

最终的答案即：$dp[0][n-1][0]$

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;
}