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

骑猪看日落 2022-04-22 02:14 554阅读 0赞

\#include <stdio.h>  
\#include <stdlib.h>  
\#define MAX(a,b) a>b?a:b

int a\[100\];  
int dp\[1000\]\[1000\];

int main()  
\{  
    int i,j,k;  
    int n,m;  
    scanf("%d %d",&n,&m);  
    for( i=1;i<=n;i++)  
    \{  
        scanf("%d",&a\[i\]);  
    \}  
    for( i=1;i<=n;i++)//分为一段  
    \{  
        dp\[i\]\[1\]=dp\[i-1\]\[1\]+a\[i\];  
    \}

for( i=1;i<=n;i++)  
    \{  
        for( j=2;j<=m;j++)  
        \{  
            int minvalue=99999;  
            for( k=1;k<i;k++)\{  
                int temp=MAX(dp\[i\]\[1\]-dp\[k\]\[1\],dp\[k\]\[j-1\]);//前i个数减去前k个数分成一段  
                if(temp<minvalue)  
                \{  
                    minvalue=temp;  
                \}  
            \}  
            dp\[i\]\[j\]=minvalue;  
        \}  
     \}

for(i=0;i<=n;i++)  
    \{  
        for(j=0;j<=m;j++)  
        \{  
            printf("%d ",dp\[i\]\[j\]);  
        \}  
        printf("\\n");  
    \}

printf("%d\\n",dp\[n\]\[m\]);

return 0;  
\}

发表评论取消回复

表情：

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

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

相关阅读

相关 C++动态规划------最大子段和的问题

目录最大子段和（动态规划C++）最大子段和的动态规划算法 4.4 最大子段和算法4.7计算最大子段和的动态规划算法算法4.8计算最大子段和的动态规划算法的

深藏阁楼爱情的钟/ 2024年03月22日 12:11/ 0 赞/ 162 阅读

相关动态规划之下降路径最小和

1. 题目分析题目链接选自力扣 : [下降路径最小和][Link 1] ![image.png][] 如果光看这个题目说明的话, 是有点抽象的. 我们结合实例

╰半夏微凉°/ 2024年03月16日 22:48/ 0 赞/ 171 阅读

相关动态规划之最小路径和

1. 题目分析题目链接选自力扣 : [最小路径和][Link 1] ![image.png][] 前面解触了很多路径题. 这依然是一个路径题, 题目要求从左上角

深碍√TFBOYSˉ_/ 2024年03月16日 22:48/ 0 赞/ 126 阅读

相关动态规划之最小路径和

[64. 最小路径和][64.] 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

àì夳堔傛蜴生んèń/ 2023年09月30日 21:14/ 0 赞/ 73 阅读

相关轻松搞定动态规划之最大子段和问题

【问题描述】给定由n个整数组成的序列a1,a2,…,a(n),求该序列字段和的最大值。分析当所有整数均为负值时定义其最大字段和为0。

布满荆棘的人生/ 2023年07月20日 05:50/ 0 赞/ 194 阅读

相关最小m段和（JAVA版）

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

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

相关 428-动态规划算法-最大子段和

题目如下 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

傷城~/ 2022年09月05日 04:27/ 0 赞/ 276 阅读

相关最大子段和动态规划实现

找到《最大子段和问题的动态规划求解》的pdf，讲解很透彻。 public class Main { public static void ma

偏执的太偏执、/ 2022年06月18日 11:08/ 0 赞/ 464 阅读

相关连续子段和问题（动态规划）

【问题描述】给出一段序列，选出其中连续且非空的一段使得这段和最大。【输入格式】输入文件的第一行是一个正整数 N，表示了序列的长度。第 2 行包含 N 个绝

冷不防/ 2022年06月08日 08:59/ 0 赞/ 280 阅读

相关动态规划之最小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 阅读