切割成本

[编程题]切割成本

热度指数：1397 时间限制：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

算法知识视频讲解

Cheukcat

这题把我读吐了，出题的爪巴

发表于 2020-03-19 18:15:37 回复(2)

offerPlusPlus_

public int attackMonster (int monsterLength, int[] monsterPoint) {
        // write code here
        Arrays.sort(monsterPoint);
        int n =  monsterPoint.length;
        int[][] dp = new int[n+2][n+2];


        int [] len = new int[n+2];
        for(int i=1;i<n+1;i++){
            len[i] = monsterPoint[i-1];
        }
        len[0]=0;
        len[n+1] = monsterLength;
        for (int i = 2; i <= n+1; i++) { //步长
            for (int j = 0; j <= n+1-i; j++) { //子区间起始点
                int initialMin=Integer.MAX_VALUE;
                for (int k = j+1; k < i+j; k++) {    //子区间各个间隔点
                    int tempV=dp[j][k]+dp[k][j+i]+len[j+i]-len[j];
                    if(initialMin>tempV){
                        initialMin=tempV;
                    }
                }
                dp[j][j+i]=initialMin;
            }
        }
        return dp[0][n+1];
    }

最优子结构：min（取中间一个间隔点，间隔点左边耗费最少能量值+间隔点右边耗费最少能量值+最右边坐标值（间隔点的能量值）-最左边坐标值（间隔点的能量值））（间隔点为任意一左坐标间隔点与右坐标间隔点间的坐标间隔点）

发表于 2020-03-23 09:56:33 回复(1)

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param monsterLength int整型 怪兽长度
     * @param monsterPoint int整型vector 怪兽攻击点位置
     * @return int整型
     */
    int attackMonster(int monsterLength, vector<int>& monsterPoint) {
        int n = monsterPoint.size();
        sort(monsterPoint.begin(), monsterPoint.end());
        int dp[n+2][n+2], a[n+2];
        memset(dp, 0, sizeof(dp));
        a[0] = 0; a[n+1] = monsterLength;
        for(int i=1;i<=n;i++)
            a[i] = monsterPoint[i-1];
        for(int i=2;i<=n+1;i++)
            for(int j=0;j<=n+1-i;j++){
                int Min = INT_MAX;
                for(int k=j+1;k<i+j;k++)
                    Min = min(Min, dp[j][k]+dp[k][j+i]+a[j+i]-a[j]);
                dp[j][j+i] = Min;
            }    
        return dp[0][n+1];
    }
};

发表于 2020-08-09 00:13:57 回复(0)

Python 3

ZhongHaoWang

经典的区间dp

class Solution:
    def attackMonster(self , n , cuts ):
        # write code here
        m = len(cuts)
        cuts = [0] + sorted(cuts) + [n]
        dp = [[0 for i in range(m + 2)] for i in range(m + 2)]

        for i in range(m, 0, -1):
            for j in range(i, m + 1):
                if i == j:
                    dp[i][j] = 0
                else:
                    dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j] for k in range(i,j + 1))
              
                dp[i][j] += cuts[j + 1] - cuts[i - 1]
        
        return dp[1][m]

发表于 2021-08-28 16:55:46 回复(0)

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)

撕裂的天堂201901140917290

#
# 
# @param monsterLength int整型 怪兽长度
# @param monsterPoint int整型一维数组 怪兽攻击点位置
# @return int整型
#
class Solution:
    def attackMonster(self , monsterLength , monsterPoint ):
        # write code here
        monsterPoint = sorted(monsterPoint)
        m = len(monsterPoint) + 1
        dp = []
        for i in range(m):
            dp.append([0 for _ in range(m)])
        monsterPoint = [0] + monsterPoint + [monsterLength]
        for i in range(1,m):
            for j in range(m-i):
                base = monsterPoint[j+i+1]-monsterPoint[j]
                minres = None
                for k in range(j,j+i):
                    if minres == None:
                        minres = base + dp[j][k] + dp[k+1][j+i]
                    else:
                        minres = min(minres,base + dp[j][k] + dp[k+1][j+i])
                dp[j][j+i] = minres
        return dp[0][-1]

发表于 2020-08-01 01:13:37 回复(0)