描述
给你连续的N个数字符，在其中插入K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
输入
程序的输入共有两行：
第一行是2个正整数N，K（6≤N≤40，1≤K≤6）
第二行是N个连续的数字符。
输出
输出所求得的最大乘积（一个自然数）。
样例输入
4 2
1231
样例输出
62
提示
1*2*31=62
分析
动态规划方法。
记F[N][M]表示长为N的序列，划分为M段的最大乘积。
那么F[N][M]=(长为J（J<N）的序列划分为M-1次的值)*（J+1到N组成的数），如下
得到动态规划方程为：
注意事项
1.范围超过int，要用64位int
2.G也是动规生成，计算i-j的数字大小
AC代码
#include<iostream>
#define MAX 50
using namespace std;
__int64 max(__int64 a,__int64 b)
{
if(a>=b)
return a;
else
return b;
}
__int64 G[MAX][MAX],dp[MAX][8],str[MAX];
int main()
{
__int64 n,m,i,j,l;
char ch;
while(scanf("%I64d%I64d",&n,&m)==2)
{
getchar();
for(i=1;i<=n;i++)
{
scanf("%c",&ch);
str[i]=ch-‘0‘;
G[i][i]=str[i];
}
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
{
G[i][j]=G[i][j-1]*10+str[j];
}
}
for(i=1;i<=n;i++)
dp[i][0]=G[1][i];
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
dp[i][j]=0;
for(l=j;l<i;l++)
{
dp[i][j]=max(dp[i][j],dp[l][j-1]*G[l+1][i]);
}
}
}
printf("%I64d\n",dp[n][m]);
}
return 0;
}
acm.njupt--1882,布布扣,bubuko.com
原文：http://blog.csdn.net/ice110956/article/details/20527039