最小m段和问题-C语言
159 浏览量
2023-11-11
16:25:57
上传
评论
收藏 358KB PDF 举报
算
法
思
路
：
前
⾯
如
何
分
段
会
直
接
影
响
⼦
序
列
和
的
最
⼤
值
，
故
应
该
枚
举
记
录
每
种
分
段
的
情
况
代
码
实
现
：
#include<bits/stdc++.h>
using namespace std;
#define N 100
int n,m;
int a[N],sum[N];
int dp[N][N]; //dp[i][j]
表
示
把
前
i
个
整数
分
成
j
段
j
段
⼦
序
列
的
和
的
最
⼤
值
最
⼩
为
多
少
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
memset(dp,0x3f,sizeof(dp));
dp[1][1]=a[1];
for(int i=1;i<=n;i++){
dp[i][1]=sum[i];
for(int j=2;j<=min(m,i);j++){
//
遍
历
第
j-1
段
的
最
后
⼀个
数
的
位
置
for(int k=j-1;k<i;k++){
dp[i][j]=min(dp[i][j],max(dp[k][j-1],sum[i]-sum[k]));
}
}
}
printf("%d",dp[n][m]);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
复
制
资源评论
