将一条长度为x的线段切成若干段,切割点已给出,每次切割的成本为切割后产生的两段线段长度之和,求最小的切割成本。
20,[2,5,10,18]
45
线段长为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;
切割点个数<300x<1000000
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]; }
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]; } };
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]
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]; }
# # # @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]