方法思路

这道题目类似于经典的“戳气球”或“消消乐”问题，需要使用动态规划来解决。关键在于如何定义状态和状态转移方程，以覆盖所有可能的消除方式。

1. 状态定义：使用 dp[i][j] 表示在砖块区间 [i, j] 内能获得的最大得分。
2. 初始化：对于长度为1的区间，只能单消，所以 dp[i][i] = a。
3. 状态转移：
   • 单消：可以消除左端或右端的砖块，得分加上剩余区间的得分。
   • 双消：如果两端的砖块颜色相同，可以消除这两个砖块，得分加上中间区间的得分。
   • 三消：如果存在中间的砖块颜色与两端相同，可以消除这三个砖块，得分加上左右两侧区间的得分。
   • 区间分割：将区间分成两部分，分别计算得分后相加，取最大值。
4. 填充顺序：自底向上，先计算小区间，再计算大区间，确保子问题已经解决。

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int a = Integer.parseInt(line[1]);
        int b = Integer.parseInt(line[2]);
        int c = Integer.parseInt(line[3]);
        
        int[] nums = new int[n];
        line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line[i]);
        }
        
        // 自底向上填充DP表
        int[][] dp = new int[n][n];
        
        // 初始化长度为1的区间
        for (int i = 0; i < n; i++) {
            dp[i][i] = a;
        }
        
        // 填充长度为2及以上的区间
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                // 单消边界
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]) + a;
                
                // 首尾颜色相同的特殊情况
                if (nums[i] == nums[j]) {
                    // 二消
                    if (len == 2) {
                        dp[i][j] = Math.max(dp[i][j], b);
                    } else {
                        dp[i][j] = Math.max(dp[i][j], dp[i+1][j-1] + b);
                    }
                    
                    // 三消 - 优化检查
                    if (len >= 3) {
                        for (int k = i + 1; k < j; k++) {
                            if (nums[i] == nums[k]) {
                                int score = c;
                                if (i + 1 <= k - 1) score += dp[i+1][k-1];
                                if (k + 1 <= j - 1) score += dp[k+1][j-1];
                                dp[i][j] = Math.max(dp[i][j], score);
                            }
                        }
                    }
                }
                
                // 区间分割 - 只在必要时检查
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
        
        System.out.println(dp[0][n-1]);
    }
}

Python

import sys

def main():
    # 读取输入 - 一次性读取所有内容
    data = sys.stdin.read().split()
    n = int(data[0])
    a = int(data[1])
    b = int(data[2])
    c = int(data[3])
    nums = list(map(int, data[4:4 + n]))
    
    # 定义dp数组
    dp = [[0] * n for _ in range(n)]
    
    # 预处理颜色位置
    color_positions = [[] for _ in range(max(nums) + 1)]
    for i, color in enumerate(nums):
        color_positions[color].append(i)
    
    # 初始化长度为1的区间
    for i in range(n):
        dp[i][i] = a
    
    # 枚举区间的左端点 - 从右到左
    for i in range(n - 1, -1, -1):
        # 枚举区间的右端点 - 从左到右
        for j in range(i + 1, n):
            # 单独消除这一块
            r = (dp[i + 1][j] if dp[i + 1][j] > dp[i][j - 1] else dp[i][j - 1]) + a
            
            # 如果区间的左右端点颜色相同
            if nums[i] == nums[j]:
                # 双消
                two_consume = dp[i + 1][j - 1] + b
                r = r if r > two_consume else two_consume
                
                # 三消 - 只检查与首尾相同颜色的位置
                color = nums[i]
                for k in color_positions[color]:
                    if i < k < j:  # k在区间内
                        score = c
                        if i + 1 <= k - 1:
                            score += dp[i + 1][k - 1]
                        if k + 1 <= j - 1:
                            score += dp[k + 1][j - 1]
                        r = r if r > score else score
            
            # 将区间划分成两块
            for k in range(i + 1, j):
                split_score = dp[i][k] + dp[k + 1][j]
                r = r if r > split_score else split_score
                
            dp[i][j] = r
    
    # 打印输出
    print(dp[0][n - 1])

if __name__ == "__main__":
    main()

C++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    // 自底向上DP
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // 初始化长度为1的区间
    for (int i = 0; i < n; i++) {
        dp[i][i] = a;
    }
    
    // 填充长度为2及以上的区间
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            
            // 单消边界
            dp[i][j] = max(dp[i+1][j], dp[i][j-1]) + a;
            
            // 首尾颜色相同的特殊情况
            if (nums[i] == nums[j]) {
                // 二消
                if (len == 2) {
                    dp[i][j] = max(dp[i][j], b);
                } else {
                    dp[i][j] = max(dp[i][j], dp[i+1][j-1] + b);
                }
                
                // 三消 - 优化检查
                if (len >= 3) {
                    for (int k = i + 1; k < j; k++) {
                        if (nums[i] == nums[k]) {
                            int score = c;
                            if (i + 1 <= k - 1) score += dp[i+1][k-1];
                            if (k + 1 <= j - 1) score += dp[k+1][j-1];
                            dp[i][j] = max(dp[i][j], score);
                        }
                    }
                }
            }
            
            // 区间分割 - 只在必要时检查
            for (int k = i; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }
    
    cout << dp[0][n-1] << endl;
    
    return 0;
}