1
已采纳
高级天翼
yes,有人，状态转移方程: f[i][a] = max(f[i][a] , f[b][a-1] * cut(b + 1,i))
呵呵，小菜一碟
1
资深光能
有人吗？
0
高级天翼
抄抄书，呵呵呵呵
0
资深光能
1227 大整数的乘积
题目描述 Description
给出一个大整数 n 和一个整数m ,要求在 n 的中间添加 m - 1 个乘号，将n分成m个部分，求出这m个部分的最大乘积。
输入描述 Input Description
第一行是一个整数T，表示有T组测试数据
接下来T行，每行有两个正整数 n，m ( 1<= n < 10^30, 0 < m <= n的位数)；
输出描述 Output Description
输出每组测试样例结果为一个整数占一行
样例输入 Sample Input
2
111 2
1111 2
样例输出 Sample Output
11
121
0
资深光能
dp，书上有
0
初级光能
创建二维数组 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
缔造者
1
0
缔造者之神
1
0
中级光能
应该是关于数论的问题
0
新手光能
请问能发一下题目吗？黄俊博
0
新手天翼
书上有高精度做法
