#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<int> color(n);
    for(int i = 0; i < n ; ++i){
        cin >> color[i];
    }
    vector<vector<int>> dp(n, vector<int>(n, 0)); // dp[i][j]索引i到j的最大得分
    // 初始化窗口为1
    for(int i = 0; i < n; ++i){
        dp[i][i] = a;
    }   
    // 初始化窗口为2
    for(int i = 0; i < n - 1; ++i){
        int j = i + 1;
        if(color[i] == color[j]){
            dp[i][j] = max(2*a, b);
        }else {
            dp[i][j] = 2*a;
        }
    }
    // 计算窗口>=3 的情况
    for(int len = 3; len <= n; ++len){
        for(int i = 0; i < n - len + 1; ++i){

            int j = i + len - 1;
            // 无条件拆分
            for(int k = i; k < j; ++k){
                dp[i][j] = max(dp[i][k] + dp[k + 1][j], dp[i][j]);
            }
            // 有条件拆分：相同颜色色块可合并拆分
            for(int k = i + 1; k < j; ++k){
                if(color[i] == color[j]){ // 区间两端颜色相同
                    if(color[k] == color[i]){
                        // 三色相同
                        dp[i][j] = max(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j - 1] + max({3*a, a + b, c}));
                    }else {
                        dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + max(2*a, b));
                    }
                }else { // 区间两端颜色不同
                    if(color[k] == color[i]){
                        dp[i][j] = max(dp[i][j], dp[i + 1][ k - 1] + max(2*a, b) + dp[k + 1][j]);
                    }
                    if(color[k] == color[j]){
                        dp[i][j] = max(dp[i][j], dp[i][k - 1] +max(2*a, b) + dp[k + 1][j - 1]);
                    }
                }
            }
        }
    }

    cout << dp[0][n - 1] << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

一、解题思路

1、人话版：当你知道由一个方块组成区间的奖励最大值，你就能算出由两个方块组成区间的奖励最大值，聪明的你，开始以此类推……

dp[i][j]含：消除 索引i到索引j位置的色块 可以获得的最大分值。

（1）单独消除每个方块的值固定 dp[i][i] = a;

（2）俩俩一组，看看一块杀俩分值大，还是一个一个杀分值大 （具体看游戏设计师的脑回路了，万一连续消除两个不给你分呢~）

（3）三个及以上一组，例如四个方块可以分成（1 + 3，2 + 2， 3 + 1）组合：

无条件遍历：别管有没有相同色块，咱就按顺序硬消

有条件遍历：先把端点中间多余的方块杀喽，再把端点处相同色块凑一起杀。

2、思想总结：从小区间的最优解，递推更大区间的最优解，无条件拆分（不合并相同颜色方块） + 有条件拆分（合并相同颜色方块）

3、备注：最开始我还初始化了窗口大小为三的情况：

// 初始化窗口为3
for(int i = 0; i < n - 2; ++i){
    int j = i + 2;

    if(color[i] == color[j] && color[i] == color[i + 1]){
        // 三个同色
        dp[i][j] = max({3*a, a + b, c});
    }else if(color[i] == color[j]){

        dp[i][j] = max(3*a, a + b);
    }else{
        // 拆成左一右二，或左二右一
        dp[i][j] = max(dp[i][i] + dp[i + 1][j],dp[i][i + 1] + dp[j][j]);
    }
}

后来发现这里的逻辑冗余，所以长度为3的时候，如 i = 0， k = 1， j = 2，出现类似于dp[i + 1][ k - 1] = dp[1][0] ，一维索引比二维索引大时初始值为0（但这么操作的话，dp初始值只能是0， 负值会影响结果），不会越界。