问题描述 今年是国际数学联盟确定的“——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：， 当N=，K=1时会有以下两种分法： *=
*= 这时，符合题目要求的结果是：*= 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输入格式 程序的输入共有两行：
第一行共有2个自然数N，K（≤N≤，≤K≤）
第二行是一个长度为N的数字串。 输出格式 输出所求得的最大乘积（一个自然数）。 样例输入
样例输出
记:
由于DP题目的解法仍不熟悉,故上网搜寻解题思路
(代码参考:https://blog.csdn.net/fine_rose/article/details/63685548)
参考代码:
#include <stdio.h>
#define MIN(X,Y) (X)<(Y)?(X):(Y) int n,k;
long long num[] = {};
long long dp[][] = {};/*可使用的数字,*号的个数*/ long long cut(int l,int r)
{
int i;
long long end = ;
for (i = l ; i <= r ;i ++)
{
end = end* + num[i];
}
return end;
} void init()
{
int i;
char tmp[] = {};
scanf("%d %d",&n,&k);
scanf("%s",&tmp);
for (i = ; i <= n ; i ++)
{
num[i] = tmp[i-]-'';
}
for (i = ; i <= n ; i ++)
{
dp[i][] = cut(,i);
}
return ;
} void find()
{
int i,j;
int a,b; for (i = ; i <= n ; i ++)/*枚举能使用数字(1-i),(至少需要2数字才可添加*号)*/
{
j = MIN(i-,k);/*枚举在能使用数字中最多能放的*个数*/
for (a = ; a <= j ; a ++)/*枚举j个乘号情况下的数字分布*/
{
for (b = a ; b < i ; b ++)/*枚举在能使用数字内的不同组合*/
{
if (dp[b][a-]*cut(b+,i) > dp[i][a])
{
dp[i][a] = dp[b][a-]*cut(b+,i);/*存放最大值*/
}
}
}
} return ;
} int main(void)
{
init();
find();
printf("%lld",dp[n][k]);
return ;
}
在过完思路后,可以发现由于会遍历不同长度下的可能结果,而我们仅仅是要长度为n时的最大乘积,显然程序做了大量的无用功
而到这里，思路也有所启发
从题目中，我们可以得到的隐藏条件是n>1,且n>k
而题目的样例输入
4 2
1231
指两个乘号,放在4个数据中间(左右两端不能放),那么
第一个乘号的可能出现位置为:1*2*3*1
第二个乘号的可能出现位置为:12*3*1 (至少已放了一个乘号)
显然，后面的乘号出现位置与前面的乘号的位置有关系，可以通过标记摆放乘号，并用递归遍历不同的乘号(dfs)
这样，我们就可以得到一种情况下的数字分割
通过查乘号的出现位置，完成数字之间的相乘，并比较最大值，将最大值保存
改进代码:
#include <stdio.h>
#define MAX 46 int n,k;
long long num[MAX] = {};/*每一位的数据存储*/
int vis[MAX] = {}; /*每一位乘号的使用标记*/
long long max = ; /*最大值存储*/ void init()
{
int i;
char tmp[MAX] = {};
scanf("%d %d",&n,&k);
scanf("%s",&tmp);
for (i = ; i <= n ; i ++)
{
num[i] = tmp[i-]-'';
}
return ;
} long long cut(int l,int r)
{
int i;
long long end = ;
for (i = l ; i <= r ;i ++)
{
end = end* + num[i];
}
return end;
} void dfs(int x)
{
/*隐藏条件:N>1,N>K*/
int i;
int a,b;/*乘号分割下的数字左右下标*/
long long tmp; if (x > k)/*乘号使用完毕*/
{
a = ,b = ;
tmp = ;
/*计算该次搜索中的数字分割后的乘积*/
for (i = ; i < n ; i ++)
{
if (vis[i])
{
b = i;
tmp *= cut(a+,b);
a = b;
}
}
tmp *= cut(a+,n);
if (tmp > max)
{
max = tmp;
}
return ;
} for (i = x ; i < n ; i ++)/*遍历不同位置的乘号*/
{
if (!vis[i])/*当前位置的乘号未使用*/
{
vis[i] = ;
dfs(x+);
vis[i] = ;
}
} return ;
} int main(void)
{
init();
dfs();
printf("%lld",max);
return ;
}