题目描述

在桌面从左至右横向摆放着 (N) 堆石子。

每一堆石子都有着相同的颜色，颜色可能是颜色 (0)，颜色 (1) 或者颜色 (2) 中的其中一种。

现在要对石子进行合并，规定每次只能选择位置相邻并且颜色相同的两堆石子进行合并。

合并后新堆的相对位置保持不变，新堆的石子数目为所选择的两堆石子数目之和，并且新堆石子的颜色也会发生循环式的变化：
- 颜色 (0+0 \to 1)
- 颜色 (1+1 \to 2)
- 颜色 (2+2 \to 0)

合并的花费为所选择的两堆石子的数目之和。

给出 (N) 堆石子以及它们的初始颜色，求最少可以将它们合并为多少堆石子，以及对应的最小合并总花费。

输入格式

第一行一个正整数 (N) 表示石子堆数。

第二行包含 (N) 个用空格分隔的正整数，表示从左至右每一堆石子的数目。

第三行包含 (N) 个值为 (0)、(1) 或 (2) 的整数，表示每堆石头的颜色。

输出格式

一行包含两个整数，用空格分隔。

其中第一个整数表示合并后数目最少的石头堆数，第二个整数表示对应的最小花费。

样例

输入

5
3 2 2 2 3
0 0 1 1 0

输出

3 9

算法1

(动态规划) $O(n^4)$

思路

1. 设 dp[i][j] 表示区间 ([i, j]) 的最优合并结果，存储一个队列 Deque<Node>，其中 Node 记录石子数和颜色信息。
2. 设 cost[i][j] 存储将区间 ([i, j]) 内的石子合并后的最小花费。
3. 状态转移：
4. 对于每个区间 ([i, j])，枚举中间分割点 k，尝试合并 dp[i][k] 和 dp[k+1][j]。
5. 需要遍历 dp[k+1][j] 的所有元素，并尝试与 dp[i][k] 的最后一个元素进行合并，若颜色相同，则合并后形成一个新堆。
6. 通过 dp[0][n-1] 计算最终答案。

时间复杂度

• 共有 (O(n^2)) 个区间，每个区间需要 (O(n)) 遍历 j，且 Deque 操作最坏情况 (O(n))。
• 最坏情况下时间复杂度为 (O(n^4))。

参考文献

无

Java 代码

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

public class Main {

    static class Node {
        int stones;
        int c;

        Node(int stones, int c) {
            this.stones = stones;
            this.c = c;
        }
    }

    static Node combineNode(Node pNode, Node qNode) {
        return new Node(pNode.stones + qNode.stones, (pNode.c + 1) % 3);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int n = Integer.parseInt(reader.readLine().trim());

        int[] stones = new int[n];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            stones[i] = Integer.parseInt(tokenizer.nextToken());
        }

        int[] colors = new int[n];
        tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            colors[i] = Integer.parseInt(tokenizer.nextToken());
        }

        @SuppressWarnings("unchecked")
        Deque<Node>[][] dp = new Deque[n][n];
        int[][] cost = new int[n][n];

        // 初始化单个元素
        for (int i = 0; i < n; i++) {
            dp[i][i] = new ArrayDeque<>();
            dp[i][i].add(new Node(stones[i], colors[i]));
        }

        for (int len = 2; len <= n; len++) {
            for (int p = 0; p <= n - len; p++) {
                int q = p + len - 1;
                int minStones = Integer.MAX_VALUE;
                int minSize = Integer.MAX_VALUE;
                Deque<Node> bestDeque = null;

                for (int j = p; j < q; j++) {
                    int nowStones = cost[p][j] + cost[j + 1][q];
                    Deque<Node> left = dp[p][j];

                    Deque<Node> newStack = new ArrayDeque<>(left);

                    for (Node node : dp[j+1][q]) {
                        while (!newStack.isEmpty() && newStack.peekLast().c == node.c) {
                            Node last = newStack.pollLast();
                            node = combineNode(last, node);
                            nowStones += node.stones;
                        }
                        newStack.addLast(node);
                    }

                    int newSize = newStack.size();

                    if (newSize < minSize || (newSize == minSize && nowStones < minStones)) {
                        minSize = newSize;
                        minStones = nowStones;
                        bestDeque = new ArrayDeque<>(newStack);
                    }
                }

                if (bestDeque != null) {
                    dp[p][q] = bestDeque;
                    cost[p][q] = minStones;
                }
            }
        }

        out.print(dp[0][n - 1].size() + " " + cost[0][n - 1]);

        reader.close();
        out.flush();
    }
}