题目链接

小明打砖块

题目描述

给定一个长度为 的、带颜色的砖块序列。消除砖块有三种操作：

  1. 消除1个砖块，得分 。
  2. 消除2个相邻的同色砖块，得分 。
  3. 消除3个相邻的同色砖块，得分 。

消除后，左右两边的砖块会靠拢，可能形成新的可消除的同色砖块组合。目标是求出消除所有砖块能得到的最大总得分。

解题思路

这是一个典型的区间动态规划问题，因其“消除后合并”的特性，与游戏“祖玛（Zuma）”的消除逻辑类似。简单的一维或二维DP状态不足以捕捉子问题之间的合并关系，我们需要一个更复杂的状态定义。

1. 预处理

  • 砖块压缩：首先，我们将连续的同色砖块压缩成“块”。例如，序列 [3, 1, 1, 2, 2, 2] 变为 [(color=3, count=1), (color=1, count=2), (color=2, count=3)]。这可以减少DP的状态空间，设压缩后有 个块。
  • 得分预计算：我们需要一个函数 来计算消除 个同色砖块的最大得分。这本身是一个小型的DP问题。 可以通过消除1、2或3个砖块得到，所以状态转移方程为： （需处理边界条件）。我们可以预计算出 到 的值。

2. 区间DP

  • 状态定义：我们定义一个三维DP状态 dp[i][j][k]，表示： 将压缩后的第 个到第 个块全部消除，并且假设在第 个块的右边，还额外“粘连”着 个与第 块颜色相同的砖块，这种情况下能获得的最大分数。 这个额外的 维度是解决问题的关键，它代表了从更外层（右侧）的子问题传递过来的、未来可能与第 块合并的砖块数量。

  • 状态转移：

    我们采用记忆化搜索的方式来计算 dp[i][j][k]。对于状态 (i, j, k)，我们主要考虑最右边的第 个块。设它本身有 count 个砖块，加上额外的 k 个，总共有 count + k 个同色砖块需要处理。

    1. 策略一：直接消除第 个块

      我们可以选择立即消除这 count + k 个砖块，获得得分 。之后，问题退化为求解子问题 dp[i][j-1][0]（因为第 块旁边没有同色块粘连了）。

      此时的总分为 dp[i][j-1][0] + S[count + k]。

    2. 策略二：将第 个块与左边的同色块合并

      我们可以寻找一个在 i 到 j-1 之间的块 p，使得 block[p].color == block[j].color。如果找到了，我们可以尝试先消除它们之间的所有块（即 [p+1, j-1]），这部分的得分为 dp[p+1][j-1][0]。

      消除后，块 p 和块 j 就相邻了。整个问题就转化为了：求解 [i, p] 区间，但是现在块 p 的右边粘连的砖块数量，是原来块 j 的 count 个，再加上原有的 k 个。

      这部分的总分为 dp[p+1][j-1][0] + dp[i][p][count + k]。

      我们需要遍历所有可能的 p，并取最大值。

    dp[i][j][k] 的值就是以上所有可能策略中得分的最大值。

  • 基本情况：

    • 如果 i > j，表示区间为空，得分为 。
    • 如果 i == j，表示只剩一个块，我们直接计算消除 block[i].count + k 个砖块的得分 。

最终的答案就是 dp[0][m-1][0]。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Block {
    int color;
    int count;
};

int n, a, b, c;
vector<Block> blocks;
// 注意：对于 n=300，三维数组会占用大量内存
// 305*305*305 * 4 bytes ≈ 113 MB
int memo[305][305][305];
long long S[305];

void precompute_scores() {
    S[0] = 0;
    for (int i = 1; i <= n; ++i) {
        S[i] = -1e18; // 初始化为极小值
        if (i >= 1) S[i] = max(S[i], S[i - 1] + a);
        if (i >= 2) S[i] = max(S[i], S[i - 2] + b);
        if (i >= 3) S[i] = max(S[i], S[i - 3] + c);
    }
}

long long solve(int l, int r, int k) {
    if (l > r) {
        return 0;
    }
    if (l == r) {
        return S[min(n, blocks[l].count + k)];
    }
    if (memo[l][r][k] != -1) {
        return memo[l][r][k];
    }

    long long res = -1e18;
    
    // 策略一: 直接消除第 r 块
    res = max(res, solve(l, r - 1, 0) + S[min(n, blocks[r].count + k)]);

    // 策略二: 向左合并
    for (int p = l; p < r; ++p) {
        if (blocks[p].color == blocks[r].color) {
            res = max(res, solve(l, p, blocks[r].count + k) + solve(p + 1, r - 1, 0));
        }
    }

    return memo[l][r][k] = res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> a >> b >> c;
    vector<int> colors(n);
    for (int i = 0; i < n; ++i) {
        cin >> colors[i];
    }
    
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    precompute_scores();

    for (int color : colors) {
        if (blocks.empty() || color != blocks.back().color) {
            blocks.push_back({color, 1});
        } else {
            blocks.back().count++;
        }
    }
    
    int m = blocks.size();
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int l = 0; l <= n; ++l) {
                memo[i][j][l] = -1;
            }
        }
    }

    cout << solve(0, m - 1, 0) << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static class Block {
        int color;
        int count;

        Block(int color, int count) {
            this.color = color;
            this.count = count;
        }
    }

    static int n, a, b, c;
    static ArrayList<Block> blocks = new ArrayList<>();
    static long[][][] memo;
    static long[] S;

    static void precomputeScores() {
        S = new long[n + 5]; // 留出余量
        S[0] = 0;
        for (int i = 1; i < S.length; i++) {
            S[i] = -1_000_000_000_000_000L; // 初始化为极小值
            if (i >= 1) S[i] = Math.max(S[i], S[i - 1] + a);
            if (i >= 2) S[i] = Math.max(S[i], S[i - 2] + b);
            if (i >= 3) S[i] = Math.max(S[i], S[i - 3] + c);
        }
    }

    static long solve(int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        int effective_k = Math.min(n, k);
        if (l == r) {
            return S[Math.min(n, blocks.get(l).count + effective_k)];
        }
        if (memo[l][r][effective_k] != -1) {
            return memo[l][r][effective_k];
        }

        long res = -1_000_000_000_000_000L;

        // 策略一: 直接消除第 r 块
        res = Math.max(res, solve(l, r - 1, 0) + S[Math.min(n, blocks.get(r).count + effective_k)]);

        // 策略二: 向左合并
        for (int p = l; p < r; p++) {
            if (blocks.get(p).color == blocks.get(r).color) {
                res = Math.max(res, solve(l, p, blocks.get(r).count + effective_k) + solve(p + 1, r - 1, 0));
            }
        }

        return memo[l][r][effective_k] = res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        int[] colors = new int[n];
        for (int i = 0; i < n; i++) {
            colors[i] = sc.nextInt();
        }

        if (n == 0) {
            System.out.println(0);
            return;
        }

        precomputeScores();

        for (int color : colors) {
            if (blocks.isEmpty() || color != blocks.get(blocks.size() - 1).color) {
                blocks.add(new Block(color, 1));
            } else {
                blocks.get(blocks.size() - 1).count++;
            }
        }
        
        int m = blocks.size();
        memo = new long[m][m][n + 1];
        for (long[][] layer1 : memo) {
            for (long[] layer2 : layer1) {
                Arrays.fill(layer2, -1);
            }
        }
        
        System.out.println(solve(0, m - 1, 0));
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(305 * 305)

memo = {}
blocks = []
S = []
n, a, b, c = 0, 0, 0, 0

def precompute_scores():
    global S
    S = [-10**18] * (n + 5) # 留出余量
    S[0] = 0
    for i in range(1, n + 5):
        if i >= 1: S[i] = max(S[i], S[i-1] + a)
        if i >= 2: S[i] = max(S[i], S[i-2] + b)
        if i >= 3: S[i] = max(S[i], S[i-3] + c)

def solve(l, r, k):
    if l > r:
        return 0
    
    # 附加的 k 不应超过 n
    effective_k = min(n, k)

    if l == r:
        return S[min(n, blocks[l][1] + effective_k)]
    
    state = (l, r, effective_k)
    if state in memo:
        return memo[state]
    
    res = -10**18
    
    # 策略一: 直接消除第 r 块
    count_r = blocks[r][1]
    res = max(res, solve(l, r - 1, 0) + S[min(n, count_r + effective_k)])
    
    # 策略二: 向左合并
    color_r = blocks[r][0]
    for p in range(l, r):
        if blocks[p][0] == color_r:
            res = max(res, solve(l, p, count_r + effective_k) + solve(p + 1, r - 1, 0))
            
    memo[state] = res
    return res

def main():
    global n, a, b, c, blocks, memo
    try:
        line = sys.stdin.readline()
        if not line: return
        n, a, b, c = map(int, line.split())
        
        if n == 0:
            print(0)
            return

        colors = list(map(int, sys.stdin.readline().split()))
        
        precompute_scores()

        if colors:
            for color in colors:
                if not blocks or color != blocks[-1][0]:
                    blocks.append([color, 1])
                else:
                    blocks[-1][1] += 1
            
            print(solve(0, len(blocks) - 1, 0))
        else:
             print(0)

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：区间动态规划 + 记忆化搜索
  • 时间复杂度：令 为压缩后的块数（）。DP状态数为 。每个状态的计算需要一个 的循环来寻找合并点。因此，总时间复杂度为 。
  • 关于 的讨论：在理论最坏情况下（例如颜色交替出现），，此时复杂度为 。对于 的数据规模，这个复杂度是无法接受的。然而，这类问题在竞赛中通常有两种可能：
    1. 存在一个更优化的 算法，但其状态定义或转移更为复杂。
    2. 测试数据不是最坏情况，即压缩后的块数 会远小于 ，使得 的算法能够通过。 本题解采用的是标准模型，其正确性有保证，但在面对极限数据时可能会超时。
  • 空间复杂度：DP的记忆化表大小为 ，这是空间占用的主要部分。在最坏情况下为 。对于 ，这可能需要超过100MB的内存，需要注意内存限制。