最小m段和（JAVA版）

太过爱你忘了你带给我的痛 2023-06-08 06:18 51阅读 0赞

给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？

样例输入

1 1

10

样例输出

10

样例输入

9 3  
9 8 7 6 5 4 3 2 1

样例输出

17

public static int getMin(int a[], int len) {
    		int dp[][] = new int[a.length][len+1];
    		for (int i = 1; i < a.length; i++) {
    			dp[i][1] = dp[i - 1][1] + a[i-1];
    		}
    		for (int i = 1; i < a.length; i++) {
    			for (int j = 2; j <= len; j++) {
    				int min = Integer.MAX_VALUE;
    				for (int k = 1; k < i; k++) {
    					if (min > Math.max(dp[i][1] - dp[k][1], dp[k][j - 1])) {
    						min = Math.max(dp[i][1] - dp[k][1], dp[k][j - 1]);
    					}
    				}
    				dp[i][j] = min;
    			}
    		}
    		for(int i=0;i<a.length;i++) {
    			for(int j=0;j<len+1;j++) {
    				System.out.print(dp[i][j]+"                 ");
    			}
    			System.out.println();
    		}
    		return dp[a.length-1][len];
    	}

思路如下面矩阵：

0                 0                 0                 0                 
    0                 9                 2147483647        2147483647                 
    0                 17                 9                2147483647                 
    0                 24                 15                 9                 
    0                 30                 17                 13                 
    0                 35                 18                 15                 
    0                 39                 22                 15                 
    0                 42                 24                 17                 
    0                 44                 24                 17

横向代表分几段0，1，2，3，4

纵向代表有几个数字。

其实这个问题和01背包很像。

发表评论取消回复

表情：

评论列表（有 0 条评论，51人围观）

还没有评论，来说两句吧...

相关阅读

相关最小m段和（JAVA版）

给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？样例输入 1 1 10

太过爱你忘了你带给我的痛/ 2023年06月08日 06:18/ 0 赞/ 52 阅读

相关 dp之最大和，m段最大和以及最大子矩阵

前一段时间因为要讲课学习了dp系列算法，学习了很多东西，给大一菜鸟讲了这个系列的算法，当时没有记录，前几天拿起来发现有点忘记了，所以在这里记录一下，最大和系列算法。首先子串

系统管理员/ 2022年09月20日 09:26/ 0 赞/ 235 阅读

相关最大子段和

问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优

雨点打透心脏的1/2处/ 2022年08月08日 06:38/ 0 赞/ 289 阅读

相关最大子段和

给定n个整数（可能包含负数）组成的序列，求该序列子段和的最大值。参考代码：常规方法1 对所有可能进行遍历，找到最终结果 include<stdio.h>

旧城等待，/ 2022年08月02日 06:44/ 0 赞/ 291 阅读

相关 Ubuntu 最小精简版

好消息！Canonical公司正式宣布──Ubuntu JeOS 7.10发布了！是不是有点懵了？什么是Ubuntu JeOS 7.10？怎么突然冒出这个发行版？还

素颜马尾好姑娘i/ 2022年07月15日 03:55/ 0 赞/ 479 阅读

相关动态规划之最小M段和问题

\include <stdio.h> \include <stdlib.h> \define MAX(a,b) a>b?a:b int a\[100\]; int

骑猪看日落/ 2022年04月22日 02:14/ 0 赞/ 555 阅读

相关最大子段和

送分题(songfen) Time Limit:1000ms Memory Limit:128MB 题目描述 LYK喜欢干一些有挑战的事，比如说求区间最大子段和。它知

港控/mmm°/ 2022年01月10日 10:53/ 0 赞/ 327 阅读

相关 51nod 1052 最大M子段和

N个整数组成的序列a\[1\],a\[2\],a\[3\],…,a\[n\]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，

旧城等待，/ 2021年12月10日 03:21/ 0 赞/ 331 阅读

相关 51nod1052最大M子段和

[1052最大M子段和][1052_M] 我们设 \\(f\[i\]\[j\]\\) 表示前 \\(i\\) 位划分为 \\(j\\) 段的答案，在此基础上再添加一维，\\(

阳光穿透心脏的1/2处/ 2021年10月29日 11:42/ 0 赞/ 352 阅读

相关 P1361 小M的作物（最小割）

题目错别字很多，且题意不清，但题目还是很好的经典的最小割模型，结果=收益和-最小割形如下面的模型有 n 个物品和两个集合 A,B，如果将一个物品放入 A 集合

港控/mmm°/ 2021年09月29日 14:28/ 0 赞/ 334 阅读