0
已解决
高级守护
给出一个大整数 n 和一个整数m ,要求在 n 的中间添加 m - 1 个乘号，将n分成m个部分，求出这m个部分的最大乘积。
怎么写 pascal
1
已采纳
高级光能
for(int i = 2;i <= n;i++){ //枚举分割为前i位数字
for(int j = 1;j <= min(i-1,k);j++){ //枚举有几个乘号
for(int k = j;k < i;k++){ //在第几位放乘号
f[i][j] = max(f[i][j],f[k][j-1] * cut(k + 1,i));
}
}
}
1
初级光能
创建二维数组 f[][] ,用 f[i][j] 表示前 i 位数包含 j 个乘号所能达到的最大乘积
- 将 i 从 2 到 n 枚举，表示分割为前i位数字
- 对每一次分割再次将 a 从 1 到 min(i-1,k) 枚举，表示前 i 位中含有 a 个乘号
- 将 b 从 a 到 i - 1 进行一次枚举，表示前 i 位中含有 a 个乘号，且最后一个乘号的位置在 b 处。那么当最后一个乘号在 b 处时最大值为前 b 位中含有 a - 1 个乘号的最大值乘上 b 处之后的数字
- 因此得出了状态转移方程 f[i][a] = max(f[i][a] , f[b][a-1] * cut(b + 1,i))
——（cut(b + 1,i) 表示 b + 1 到 i 位数字） - //核心代码如下
- for(int j=1;j<=lenth;j++)
g[j]=n[j-1]-'0';
for(int j=1;j<=lenth;j++)
f[j][0]=cut(1,j);
for(int j=2;j<=lenth;j++)
for(int a=1;a<=min(j-1,m-1);a++)
for(int b=a;b<=j-1;b++)
f[j][a]=max(f[j][a],f[b][a-1]*cut(b+1,j));
cout<<f[lenth][m-1]<<endl; - 前面还有一段把字符转换数字的小函数，就由你来完成了,祝你最后ac
- 望采纳，谢谢
0
高级守护
快
0
高级天翼
是Pascal@夏子健 @梁锦程
0
资深天翼
1
