乘积最大问题？？？

设有一个长度为N的数字串，要求使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

 

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

 

有一个数字串：312， 当N=3，K=1时会有以下两种分法：

 

1）    3*12=36

2）   31*2=62

   

   这时，符合题目要求的结果是：31*2=62

 

   现在，请你设计一个程序，求得正确的答案。


输入


 程序的输入共有两行：

 第一行共有2个自然数N，K（6≤N≤10，1≤K≤6）

 第二行是一个长度为N的数字串。


输出

输出所求得的最大乘积（一个自然数）,答案在long long 数据范围之内。

样例输入

4  2
1231


样例输出

62




请高手们给点思路~~~~~~~~~~~~~~~

18 个解决方案

#1

dp.
dp[m...n]=max{dp[m...k]*dp[k+1...n]}  (m<=k<=n)

#2

王道。。。

#3

#include <iostream>
using namespace std;

long dup(char *num, int n, int k);

int main()
{
	char *num = "1231";
	cout << dup(num, strlen(num), 2) << endl;
	system("pause");
	return 0;
}

long dup(char *num, int n, int k)
{
	int max = 0;
	int t1, t2;

	if (n <= k)
	{
		return -1;
	}

	if (k == 0 || n == 1)
	{
		for (int i = 0; i < n; i++)
		{
			max *= 10;
			max += num[i] - '0';
		}
		return max;
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < k; j++)
		{
			t1 = dup(num, i, j);
			if (t1 < 0)
			{
				continue;
			}
			t2 = dup(num + i, n - i, k - j - 1);
			if (t2 < 0)
			{
				continue;
			}
			if (max < t1 * t2)
			{
				max = t1 * t2;
			}
		}
	}
	return max;
}

#4

呃，修改一处：

if (t1 < 0) 
{
    break;
}

#5

可以自底向上算更好吧？？？

#6

没仔细想过，
1. 各个乘数的位数应该接近
2. 最高位应该是前k个最大数依次分配
3. 次高位应该是剩下的k个最大数依次分配（不足就少一位）
依次类推
假定N=k*m，则结果复杂度可能是(k!)^m，小于N!

如果应用排序不等式 a<b, c<d
(10a+c)(10b+d) - (10a+d)(10b+c)
=100ab+10ad+10bc+dc-100ab-10ac-10bd-dc
=10[ad+bc-(ac+bd)] 
<0

因此总是大的跟大的结合，小的跟小的结合乘积最大，这样几乎不需要排列和循环了，只要把N个数排序即可

#7

这题贪心应该就可以了,DP可能反而复杂了!

找出串中从第2个数开始最大的N个应该就行,同样大的话,再比下一位,下一位应当小于等于当前位,如果大于的话应当先被切分了!

#8

又仔细想了一下,贪心有问题,还是得用DP才行!

#9

如果“乘法”是个特别慢的过程，则还是可以考虑贪心算法。可惜，时间主要是花在分解字串。

#10

DP怎么弄？？？？ 乘号数怎么分呢？？

#11

再次考虑了一下,还是可以用贪心,但应当是从第3位开始找n-1个,最后再从头试到尾找一个!
这样的话就不会出现,

19876

最大是19*8*76而不是1*9*876

用DP大概应该是先找到第1个,然后再以第1个为基准找第2个,一直找到第k个

引用 10 楼 nandizhu 的回复:

DP怎么弄？？？？ 乘号数怎么分呢？？

#12

这是用DP来解的,跟3楼的差不太多,只不过加了个hash做记录用!
没仔细测试,不知道有什么BUG没有

        private void button5_Click(object sender, EventArgs e)
        {
            string strNum = "123734958127836423";
            int multiCount = 5;
            long[, ,] matrix = new long[strNum.Length, strNum.Length, multiCount + 1];
            long m = maxMuti(matrix, strNum, 0, strNum.Length - 1, multiCount);
        }

        private long maxMuti(long[, ,] matrix, string str, int start, int end, int multicount)
        {
            if (end - start < multicount)
                return 0;

            if (matrix[start, end, multicount] > 0)
                return matrix[start, end, multicount];

            if (multicount == 0)
                return Convert.ToInt64(str.Substring(start,end - start + 1));

            if (end - start == multicount)
            {
                long rValue = 1;
                for (int i = start; i < end; i++)
                    rValue *= Convert.ToInt64(str.Substring(i, 1));

                matrix[start, end, multicount] = rValue;
                return rValue;
            }

            long max = 0;
            long value;
            long lPart;

            for (int i = start + multicount; i < end; i++)
            {
                lPart = Convert.ToInt64(str.Substring(i + 1,end - i));
                value = maxMuti(matrix,str,start,i,multicount - 1);
                value *= lPart;
                if (value > max)
                    max = value;
            }

            matrix[start, end, multicount] = max;
            return max;
        }

#13

怎么DP的，能不能说一下思路，这个题不用穷举就可以做吗？

#14

DP(1,N,K)表示从第1到第N位,加入K个乘号

DP(1,N,K) = Max(DP[1,k,k-1]*DP[k,n,0],DP[1,k+1,k-1]*DP[k+1,n,0]......DP[1,n-1,k-1]*DP[n-1,n,0]);

其实这道题用贪心，主要是在处理第一个乘号以及相同数字的时候不好办，否则要比DP简单不少，可能结合一下效率是最高的，不过程序就复杂了。

引用 13 楼 iwantnon 的回复:

怎么DP的，能不能说一下思路，这个题不用穷举就可以做吗？

#15

哦，明白了

#16

这里我有算法 我命名为“细胞竞争分裂法” 具体实现我已经用JAVA做出了 经过测试 跟穷举法得出的结果是一致的 而时间复杂度没有仔细算过 但绝对是P解法 比穷举法好很多 60多个数字 40个乘号 一点即出结果
具体思路如下：
1、把数字串视为细胞，它有一个最大乘积点，这样分裂了成两个细胞；
2、重复第一步，把分裂出来的两个细胞各自求出最大乘积点，然后用各自的乘积除以各自的数字串，比率最大的分裂；
3、重复第三步，直到乘号数为0；

举个例子：数字串“399987”，两个乘号
这个数字串的最大的乘积点是“399*987”，第一个乘号插在这，然后分裂成两个子数字串“399”和“987”，这两个子数字串各自的最大的乘积点分别是“39*9”和“9*87”，这个时候选择谁插入呢？
用39*9/399和9*87/987比较，哪个比率最大，就选择这个插入。插入之后继续算出分裂出来的两个子细胞的最大乘积点和比率，以此类推。这个例子是39*9/399大，因此最后结果是：39*9*987

这个算法不是乱来的，是可以推导的。至于代码我就不贴出了。
说起来，这个题用递归+暴力穷举让人蛋疼，经测试，数字串长度超过30，乘号数10，就已经out of memory了，就算改进一下空间复杂度，穷举始终是非P问题，等得让人蛋疼。

#17

16楼 ：请问如何找最大乘积点  那样是不是会out of memory

#18

引用 17 楼  的回复:

16楼 ：请问如何找最大乘积点 那样是不是会out of memory

我代码都已经写出了，没有out of memory问题，你觉得我这个算法哪里会导致这个问题出现？
当然如果你是要求一个长度大到上亿的数字串，那没的说。=。=