题解 | 气球谜题

1. 暴力美学：对所有的序列进行遍历（一共14中），对气球砍两刀（最多）组成三段，并计算花费时间。用前缀和计算每一段的花费。在遍历中还需要i，j两刀（两层遍历），加和3段花费时间。但暴力会超时，需要对i/j两刀进行优化。优化思路：

目标是：ABC表示三种颜色
[0...i] → A
[i+1...j] → B
[j+1...n-1] → C
总花费时间：
totalTime = cost(A, 0~i) + cost(B, i+1~j)  + cost(C, j+1~n-1)
其中：
cost(A, 0~i) = cost[A][i]
cost(B, i+1~j) = cost[B][j] - cost[B][i]
cost(C, j+1~n) = cost[C][n] - cost[C][j]
总花费时间：totalTime =
  cost[A][i]
+ (cost[B][j] - cost[B][i])
+ (cost[C][n] - cost[C][j]) 
 
== (cost[A][i] - cost[B][i])  // 只与i相关
+ cost[B][j]                  // 只与j相关
+ (cost[C][n] - cost[C][j])   // 只与j相关
相当于 totalTime = f(i) + g(j)
而最终目标是求totalTime的最小值 minTotalTime，也就是说在j确定之后，minTotalTime = min（f(i)） + g(j)
. 所以，这里就可以把i循环给优化掉。
只有把两层循环优化掉一层，才不会超时~~~

还有一种解法就是状态压缩dp，适合于颜色组合不好枚举的情况，但是也只能处理颜色种类小于15的规模。问题规模对于颜色种类来说是指数级别的！因为本题目就三种颜色，所以可以枚举颜色组合并手动写状态转移，见其他题解~

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        String s = sc.next();
        int[] t = new int[n];

        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
        }

        System.out.println(solve(n, s, t));
    }

    public static long solve(int n, String s, int[] t) {
        // 预处理：cost[c][i] = 前i个变成颜色c的代价
        long[][] cost = new long[3][n + 1];

        for (int i = 1; i <= n; i++) {
            int color = s.charAt(i - 1) - '0';
            for (int c = 0; c < 3; c++) {
                cost[c][i] = cost[c][i - 1];
                if (color != c) {
                    cost[c][i] += t[i - 1];
                }
            }
        }

        int[][] perms = {
                {0,1,2}, {0,2,1},
                {1,0,2}, {1,2,0},
                {2,0,1}, {2,1,0}
        };

        long ans = Long.MAX_VALUE;

        for (int[] p : perms) {
            ans = Math.min(ans, calc(n, cost, p));
        }

        return ans;
    }

    // 固定顺序 p[0] -> p[1] -> p[2]
    private static long calc(int n, long[][] cost, int[] p) {
        long res = Long.MAX_VALUE;

        long best = Long.MAX_VALUE;

        for (int j = 0; j <= n; j++) {
            if (j > 0) {
				// 计算对于该j的最小'cost[p[0]][j - 1] - cost[p[1]][j - 1]'，即第一段的花费。
                best = Math.min(best,
                        cost[p[0]][j - 1] - cost[p[1]][j - 1]);
            } else {
                best = 0;
            }

            long cur = best
                    + cost[p[1]][j]
                    + (cost[p[2]][n] - cost[p[2]][j]);

            res = Math.min(res, cur);
        }

        return res;
    }
}