切割成本

[编程题]切割成本

热度指数：1391 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。

示例1

输入

20,[2,5,10,18]

输出

说明

线段长为20，切割点为[2,5,10,18]。
第一种方案：
1.先切开第一个点，成本为2+18=20
2.切开第二个点，成本为3+15=18
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 18 + 15 + 10 = 63;
第二种方案：
1.先切开第一个点，成本为5+15=20
2.切开第二个点，成本为2+3=5
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 5 + 15 + 10 = 50;

备注:

切割点个数<300
x<1000000

算法知识视频讲解

Java

哦，好吧

使用动态规划，和 leetcode的戳气球等问题差不多

    public int attackMonster (int monsterLength, int[] monsterPoint) {
        // write code here
        // 直接动态规划
        // 用 dp[i][j] 表示 monsterPoint(i...j)之间的切割点的最小成本 ，这里是开区间
        // base case  dp[i][i] = monsterLength;
        // 状态转移
        // dp[i][j] =  dp[i][k] + dp[k][j] + (以k为切割点,i j 为边界的成本)
        Arrays.sort(monsterPoint);
        int n = monsterPoint.length;
        int [] scale = new int[n+2];
        // 添加 0 和 monsterLength 切割点
        scale[0]=0;
        scale[n+1] = monsterLength;
        for(int i=1;i<=n;++i){
            scale[i]=monsterPoint[i-1];
        }
        int [][] dp = new int[n+2][n+2];
        //base case
        for(int i=0;i<=n+1;++i){
            dp[i][i] = monsterLength;
        }
        // status change
        for(int i=n;i>=0;--i){
            for(int j=i+1;j<=n+1;++j){
                if (j-i==1){dp[i][j]=0;}
                else{
                    dp[i][j] = Integer.MAX_VALUE;
                    for(int k=i+1;k<j;++k){
                        int spice = dp[i][k] + dp[k][j]
                                + (scale[k]-scale[i])
                                + (scale[j]-scale[k]);
                        dp[i][j] = Math.min(spice,dp[i][j]);
                    }
                }
            }
        }
        return dp[0][n+1];
    }

发表于 2021-04-03 09:58:08 回复(0)