设有一个长度为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
\#include "stdafx.h"\
\
/\*\
设有一个长度为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 \
\*/\
char \*g\_iFactors[100];\
int g\_Elements[100];\
long long GetMaxProduct( char \*szStr, int n, int k, char \*szCurStr, int curIdx ){\
long long result = 1;\
// 用k个乘号分割成k+1段.\
if( curIdx \> k )\
{\
// 将所有字符串转换为整数.\
for( int i = 0; i \< k; i++ )\
{\
char \*pCur = g\_iFactors[i];\
char \*pNext = g\_iFactors[i+1];\
int value = 0;\
while( pCur \< pNext ){\
value = value\*10 + \*pCur - '0';\
pCur++;\
}\
\
// 存储结果.\
result \*= value;\
}\
\
char \*p = g\_iFactors[k];\
int value = 0;\
while( \*p != '\\0' ){\
value = value\*10 + \*p - '0';\
p++;\
}\
\
result\*= value;\
\
return result;\
}\
\
for( int i = 0; i \< n; i++ ){\
g\_iFactors[curIdx] = szCurStr + i;\
result = std::max( GetMaxProduct(szStr, n - i - 1, k, szCurStr + i + 1, curIdx + 1), result );\
}\
\
return result;\
}\
\
int main(){\
int n, k;\
char szStr[11];\
\
cin \>\> n \>\> k;\
cin \>\> szStr;\
cout \<\< GetMaxProduct( szStr, n, k, szStr, 0 ) \<\< endl;\
}\
\
/\*\
3 1\
312\
62\
\
4 2\
1231\
62\
请按任意键继续. . .\
\*/