Java 代码

import java.util.*;

public class Main {
    public static int N = 110;
    public static int M = 10;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] w = new int[N];
        for (int i = 1; i <= n; i++) {
            w[i] = in.nextInt();
            w[i+n] = w[i];
        }
        int[][][] f = new int[N][N][M];
        int[][][] g = new int[N][N][M];

        // 求前缀和
        int[] s = new int[N];
        for (int i = 1; i <= 2*n; i++) {
            s[i] = s[i-1] + w[i];
        }

        // 初始化
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Arrays.fill(f[i][j], Integer.MAX_VALUE);
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Arrays.fill(g[i][j], Integer.MIN_VALUE);
            }
        }

        // 枚举区间长度
        for (int len = 1; len <= n; len++) {
            for (int l = 1; l + len - 1 <= 2 * n; l++) {
                // 区间的右端点
                int r = l + len - 1;
                // 当 m=1，l..r 区间分为 1 组，对前缀和取模即可
                f[l][r][1] = g[l][r][1] = getMod(s[r] - s[l-1]);
                // 枚举分组情况，1个分组已经求出来了，所以从 2 开始枚举
                for (int k = 2; k <= m; k++) {
                    // 根据最后一个区间的情况来进行递推，j 表示前 k-1 个分组的右端点
                    // 因为前面部分区间要划分为 k-1 组的，区间长度至少为 k-1
                    // 对应的右端点为 l + k - 2，即最后一个区间是 [j+1, r], 对应的前缀和为 s[r] - s[j]
                    for (int j = l + k - 2; j < r; j++) {
                        f[l][r][k] = Math.min(f[l][r][k], f[l][j][k-1] * getMod(s[r] - s[j]));
                        g[l][r][k] = Math.max(g[l][r][k], g[l][j][k-1] * getMod(s[r] - s[j]));
                    }
                }
            }
        }

        int maxv = Integer.MIN_VALUE;
        int minv = Integer.MAX_VALUE;
        // 遍历每个长度为 n 的区间
        for (int i = 1; i <= n; i++) {
            maxv = Math.max(maxv, g[i][i+n-1][m]);
            minv = Math.min(minv, f[i][i+n-1][m]);
        }

        System.out.println(minv);
        System.out.println(maxv);
    }

    public static int getMod(int x){
        return (x % 10 + 10) % 10;
    }
}