A25811. 最大值
填空题
中等
知识点
题目描述
最大值
题目描述
给定一个正整数M(1≤M≤5)和一个只包含数字的字符串(5<字符串长度≤20)。使用M个乘号插入到字符串中，且两个乘号不能相邻，插入后生成一个乘法算式。找出一种使乘法算式数值最大的插入方式，并将结果输出。 (乘号不能放在字符串的首尾位置)
如M=2,字符串为123456,插入2个乘号。插入方式有：
1*2*3456=6912,1*23*456=10488,1*234*56=13104,1*2345*6=14070,12*3*456=16416,12*34*56=22848,12*345*6=24840,123*4*56=27552,123*45*6=33210,1234*5*6=37020,
其中乘法算式数值最大是第十种，为37020。
输入描述
第一行输入一个正整数M(1≤M≤5),表示乘号个数。
第二行输入一个只包含数字的字符串(5<字符串长度≤20),表示要插入M个乘号的字符串。
输出描述
输出一个整数，表示最大乘积数值。
样例输入
2
123456样例输出
37020参考答案
#include <iostream>
#include <string.h>
const int maxn = 41;
int n[maxn], len;
long nn(int t, int z) {
int i;
long a = n[t];
for (i = t + 1; i <= z; i++) {
a = a * 10 + n[i];
}
return a;
}
int main(void) {
int i, N, c, k, t;
long num, f[maxn][maxn];
char s[maxn];
scanf("%d%d", &N, &c);
scanf("%s", s);
len = strlen(s);
for (i = 0; i < len; i++) {
n[i] = s[i] - '0';
}
k = 0;
f[0][0] = n[0];
for (int i = 1; i < len; i++) {
f[i][0] = f[i - 1][0] * 10 + n[i];
}
k = 1;
for (k = 1; k <= c; k++) {
for (i = k; i < len; i++) {
long a = -1;
for (t = k - 1; t < i; t++) {
num = nn(t + 1, i);
long b = f[t][k - 1] * num;
if (a < b)
a = b;
}
f[i][k] = a;
}
}
printf("%d\n", f[len - 1][c]);
return 0;
}
上一题
下一题