题解 | 能量项链

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = in.nextInt();
        }
        final int MOD = 1000000007;
        int size = 2 * n;
        long[][] dp = new long[size][size];

        for (int l = 2; l <= n; l++) { 
            for (int i = 0; i <= size - l; i++) { 
                int j = i + l - 1; 
                for (int k = i; k < j; k++) { 
                    int current = h[i % n] * h[(k + 1) % n] * h[(j + 1) % n];
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k + 1][j] + current);
                }
            }
        }
        long max = 0;
        for (int i = 0; i < n; i++) {
            int j = i + n - 1;
            if (j >= size) {
                continue;
            }
            if (dp[i][j] > max) {
                max = dp[i][j];
            }
        }

        System.out.println(max % MOD);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取珠子数量 n 和每个珠子的头标记值。
2. 动态规划数组初始化：dp[i][j] 表示合并从 i 到 j 的珠子的最大能量。
3. 动态规划填充：遍历所有可能的区间长度，计算每个区间的最大能量。
4. 结果查找：遍历所有可能的起点，找到长度为 n 的区间的最大能量值，并输出结果对 10^9 + 7 取模后的值。