给定一个正整数 M (1≤M≤5)和一个只包含数字的字符串(5<字行串长度≤20)。使用 M 个乘号插入到字符串中,且两个乖号不能相邻,插入后生成一个乘法算式,找中一种使乘法算式数值最大的插入方式,并将结果输出。(乘号不能放在字符串的首尾位置)
如M=2,字符申为 123456,插入2个乘号。插入方式有:
1×2×3456=6912,1x23×456=10488,1×234×56=13104,1×2345x6=14070, 12x3x456=16416,12×34×56=22848,12x345x6=24840,123x4x56=27552, 123x45×6=33210,1234x5×6=37020, 其中乘法算式数值最大是第十种,为 37020。
输入描述:
第一行输入一个正整数 M (1≤M≤5),表示乘号个数
第二行输入一个只包含数字的字符串(5<字符串长度≤20),表示要插入M 个乘号的字符串
输出描述:
输出一个整数,表示最大乘积数值
输入数据 1
2
123456
输出数据 1
37020
#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int main()
{
double f[30][20] = {0}, d;
int a[30] = {0}, i, j, k, m, n, r, c[30][20] = {0}, b[20];
char l[30];
scanf("%d", &r);
scanf("%s",l);
n = 0;
while(l[n] != '\0'){
//字符转换成数字
a[n] = l[n] - 48;
n++;
}
//边界初始化
for (i = 0; i < n - r; i++)
{
for (d = 0, j = 0; j <= i; j++)
d = d * 10 + a[j];
f[i][0] = d;
}
//递推
for (j = 1; j <= r; j++)
{
for (i = j; i < n - r + j; i++)
{
for (k = j; k < i; k++)
{
for (d = 0, m = k + 1; m <= i; m++)
d = d * 10 + a[m];
if (f[i][j] < f[k][j-1] * d)
{
f[i][j] = f[k][j-1] * d;
//保存乘号的位置
c[i][j] = k;
}
}
}
}
//打印最优解
b[r] = c[n-1][r];
for(j = r - 1; j > 0; j--)
b[j] = c[b[j+1]][j];
for (j = 1, i = 0; j <= r; j++)
{
while (i <= b[j])
printf("%c", l[i++]);
printf(" * ");
}
printf(" = %0.0f\n", f[n-1][r]);
}
如果序列为3位数,则会输出0