环形石子归并问题

Description

本题链接:HDOJ 3506 Monkey Party

这是之前的石子归并k=2的情况下的变体。石子是按照环形排布的。

Solution

对于这道题,我们将环化成直线。设一共有n堆石子堆,将前n-1堆拷贝到n+1开始的位置即可。

比如[2, 3, 6, 7, 5, 4, 7],拷贝之后变成了[2, 3, 6, 7, 5, 4, 7, 2, 3, 6, 7, 5, 4, 7]。

那么我们让i从0到n遍历,j的长度始终设为n。保证任何情况下[i, j]都是环中的一种取值情况,并求最优解即可。

因此,仍然按照石子归并的基础模板,总长度为2n-1,最后对每一个长度为ndp[i][i + n - 1]的区间求最小值即可。

    public int mergeStones(int[] stones, int K) {
        int n = stones.length;
        int[][] dp = new int[2*n + 1][2*n + 1];
        int[] sum = new int[2*n + 1];
        for (int i = 1; i <= 2*n; i++) {
            sum[i] = stones[i - 1] + sum[i - 1];
        }
        for (int len = 2; len <= 2*n; len++) {
            for (int i = 1; i <= 2*n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i<= n; i++)
            res = Math.min(res, dp[i][i + n - 1]);
        return res;
    }

1 条评论

  • 第一篇 单调栈 – Yuxiang's Blog 2020年3月27日 回复

    […] 这里我们化圈为直,将大小为n的环形数组转换成大小为2*n – 1的数组。这个思想在前面分析区间dp中的环形石子归并题目中也有用到。 […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号