最小m段和问题
给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？
样例输入
1 1
10
样例输出
10
样例输入
9 3
9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1
样例输出
17
解：
最小m段和问题：
使用dp[i][j]放置将前i个数分成j段的最小最大值
所以dp[i][1]就是前i个数的和，dp[i-1][1]+a[i];
当j>1的时候，加定前k个数为j-1段，从k~i为第j段
所以前j-1段的最小最大值为：dp[k][j-1](前k数分为j-1段)
最后一段为：dp[i][1]-dp[k][1](前i个数减去前k个数分成一段)
这两个数种取最大值，当所有分段情况完成之后，选出最小值作为dp[i][j]的值
所以递推公式为：
dp[i][j] = min{max{dp[i][1]-dp[k][1],dp[k][j-1]}}
#include <stdio.h> #define MAX(a,b) a>b?a:b int a[100]; int dp[1000][1000]; int main() { int n,m,maxvalue=0; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { dp[i][1]=dp[i-1][1]+a[i]; } for(int i=1;i<=n;i++) { for(int j=2;j<=m;j++) { int minvalue=99999; for(int k=1;k<i;k++){ int temp=MAX(dp[i][1]-dp[k][1],dp[k][j-1]); if(temp<minvalue) { minvalue=temp; } } dp[i][j]=minvalue; } } printf("%d\n",dp[n][m]); return 0; } 今天的文章 最小m段和问题分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/92209.html