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

13

 

思路

记忆化搜索,我们定义 $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;
    }