博主主页：Yu·仙笙
专栏地址：洛谷千题详解
目录
--------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------
题目描述
今年是国际数学联盟确定的“ 2000 ――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为 N 的数字串，要求选手使用 K 个乘号将它分成 K+1个部分，找出一种分法，使得这 K+1 个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当 N=3,K=1 时会有以下两种分法：
- 3×12=36
- 31×2=62
这时，符合题目要求的结果是: 31×2=62
现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。
--------------------------------------------------------------------------------------------------------------------------------
输入格式
程序的输入共有两行：
第一行共有 2 个自然数 N,K（6≤N≤40,1≤K≤6）
第二行是一个长度为 N 的数字串。
--------------------------------------------------------------------------------------------------------------------------------
输出格式
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
--------------------------------------------------------------------------------------------------------------------------------
输入输出样例
输入 #1
4 2 1231输出 #1
62
--------------------------------------------------------------------------------------------------------------------------------
解析：
用一个数组cut[i][j]存储在第i个数字后放第j个乘号，第1到第i个数的乘积的最大值。
如果j=k，说明所有的乘号都已经放完，那么ans[i]就表示最后一个乘号放在第i个数后面的最大值，此时要乘上后面的数。因为后面的数是一定的，cut[i][j]是已知的最大值，所以ans[i]可以由唯一的路径转移。
最后比较所有的ans[i]，选择最大值输出。
完成以上步骤需要至少三个操作：
1.取数 将没有乘号分隔的连续的数字变成一个数，进行运算
2.比较 没有比较哪来的最大值
3.乘法 将乘号两边取到的数乘起来
由于n<=40，所以这些操作要用高精度的方式进行
（如果有能存40位的数据类型，请不必往下翻了，本蒟蒻最多知道一个long long）
下面上代码
--------------------------------------------------------------------------------------------------------------------------------
C++源码：
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,a[50];
char s[50];
struct node{//用结构体储存数组；当然，也可以直接用三维数组，不过感觉这样更容易理解
int v;bool exi;//v:数位,exi:是否存在
int c[50];//高精度数组
}cut[50][10],ans[50];
node culc(int l,int r){//取数操作，注意：要从右往左取，因为高精度数组是从低位往高位排的，而读入的数字串是从高位到低位
node e;
e.v=r-l+1;e.exi=true;
for(int i=1;i<=e.v;i++){
e.c[i]=a[r-i+1];
}
return e;
}
node mul(node e1,node e2){//高精度乘法
node emul;
emul.exi=true;emul.v=e1.v+e2.v-1;
for(int i=1;i<=emul.v;i++) emul.c[i]=0;
for(int i=1;i<=e1.v;i++)
for(int j=1;j<=e2.v;j++)
emul.c[i+j-1]+=e1.c[i]*e2.c[j];
int q=0;
for(int i=1;i<=emul.v;i++){
emul.c[i]+=q;
q=emul.c[i]/10;
emul.c[i]%=10;
}
while(q>0){
emul.c[++emul.v]=q%10;
q/=10;
}
return emul;
}
node Max(node e1,node e2){//高精度比较，类似字符串（然而如果是字符串的话我就直接strcmp了）
if(!e1.exi||e1.v<e2.v) return e2;
if(!e2.exi||e2.v<e1.v) return e1;//先比较是否存在和位数
for(int i=e1.v;i>=1;i--){//都存在，且位数相同，则逐位比较
if(e1.c[i]>e2.c[i]) return e1;
else if(e2.c[i]>e1.c[i]) return e2;
}
return e1;
}
int main(){
scanf("%d%d",&n,&k);
scanf("%s",s);
for(int i=0;i<n;i++) a[i+1]=s[i]-'0';//将字符串变为数字数组
for(int i=1;i<=n;i++){
ans[i].exi=false;
for(int j=1;j<=k;j++) cut[i][j].exi=false;
}
for(int i=1;i<n;i++){
cut[i][1]=culc(1,i);//只放一个乘号的话不需要转移
for(int j=2;j<=k;j++){
for(int fr=j-1;fr<i;fr++){//因为第i个数后放置的乘号最多是第i个，所以从j-1枚举front（前置位）
if(cut[fr][j-1].exi) cut[i][j]=Max(cut[i][j],mul(cut[fr][j-1],culc(fr+1,i)));
}
} //转移状态
if(cut[i][k].exi){
ans[i]=mul(cut[i][k],culc(i+1,n));
}
}
node lastans;lastans.exi=false;
for(int i=1;i<n;i++){
node tmp=Max(ans[i],lastans);
lastans=tmp;//不知道为什么，直接写lastans=Max(lastans,ans[i])总是会错，然而加一个中间变量就过了。。
}
for(int i=lastans.v;i>=1;i--) printf("%d",lastans.c[i]);//输出
return 0;
}//写完注释感觉就像白痴代码一样啊。。。（内心：那你还写了半个上午？？？）--------------------------------------------------------------------------------------------------------------------------------
Python源码：
n, k = map(int, input().split())
s = int('1' + input())
f = [[0 for i in range(k + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
f[i][0] = int(str(s)[1: i + 1])
for k1 in range(1, k + 1):
for i in range(k1 + 1, n + 1):
for j in range(k1, i):
f[i][k1] = max(f[i][k1], f[j][k1 - 1] * int(str(s)[j + 1:i + 1]))
print(f[n][k])--------------------------------------------------------------------------------------------------------------------------------
Pascal源码：
var
n,k,i,j,i1,i2,i3:longint;
f,sum:array[0..100,0..100] of ansistring;
s:string;
function gjc(a1,b1:string):string;
var
lena,lenb,lenc:longint;
i,j,x:longint;
a,b,c:array[0..200] of longint;
k:string;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0); //重置数组
fillchar(c,sizeof(c),0);
lena:=length(a1); lenb:=length(b1);
for i:=1 to lena do a[lena-i+1]:=ord(a1[i])-48; //转化为数字
for i:=1 to lenb do b[lenb-i+1]:=ord(b1[i])-48;
for i:=1 to lena do
begin
x:=0; //高精度运算
for j:=1 to lenb do
begin
c[i+j-1]:=a[i]*b[j]+x+c[i+j-1];
x:=c[i+j-1] div 10;
c[i+j-1]:=c[i+j-1] mod 10;
end;
c[i+j]:=x;
end;
lenc:=i+j;k:='';
while (c[lenc]=0) and (lenc>1) do dec(lenc);
for i:=lenc downto 1 do k:=k+chr(c[i]+48);
exit(k); //返回字符串
end;
function max(a,b:string):string; //比较字符串的大小
var
lena,lenb:longint;
begin
lena:=length(a); lenb:=length(b);
if (lena>lenb) then exit(a);
if (lena<lenb) then exit(b);
if (lena=lenb) then
if (a>b) then exit(a)
else exit(b);
end;
begin
readln(n,k);
readln(s);
for i:=1 to n do
for j:=1 to n do
sum[i,j]:=copy(s,i,j-i+1); //直接拷贝，当字符串处理
for i:=1 to n do f[i,0]:=sum[1,i]; //初始化
for i1:=1 to k do
for i2:=i1+1 to n do
for i3:=i1 to i2-1 do
f[i2,i1]:=max(f[i2,i1],gjc(f[i3,i1-1],sum[i3+1,i2])); //高精计算返回字符串比较
writeln(f[n,k]);
end.--------------------------------------------------------------------------------------------------------------------------------
Java源码：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
// long sta = System.nanoTime();
InputStream is = System.in;
OutputStream os = System.out;
IN cin = new IN(is);
PrintWriter cout = new PrintWriter(os);
SO so = new SO();
so.solution(cin, cout);
// long end = System.nanoTime();
// cout.println("耗时：" + (double)(end-sta)/1e6 + "ms");
cout.close();
}
static final int MOD = (int)1e9 + 7;
static class SO {
void solution(IN cin, PrintWriter cout) {
int N = cin.nextInt(), K = cin.nextInt();
BigInteger[][] num = new BigInteger[N][N];
BigInteger[][] dp = new BigInteger[N][K+1];
//初始化num数组
char[] cs = cin.next().toCharArray();
for(int i=0;i<N;++i) {
num[i][i] = BigInteger.valueOf(cs[i]-'0');
for(int j=i+1;j<N;++j) {
num[i][j] = num[i][j-1].multiply(BigInteger.TEN).add(BigInteger.valueOf(cs[j]-'0'));
}
}
//计算dp
for(int i=0;i<N;++i)
dp[i][0] = num[0][i];
for(int i=0;i<N;++i) {
for(int k=1;k<=(i<K?i:K);++k) {
dp[i][k] = BigInteger.ZERO;
for(int j=k-1;j<i;++j) {
BigInteger one = dp[j][k-1].multiply(num[j+1][i]);
dp[i][k] = one.compareTo(dp[i][k])>0?one:dp[i][k];
}
}
}
cout.println(dp[N-1][K]);
}//end solution
}//end SO
//以下是快读部分
static class IN {
private BufferedReader reader;
private StringTokenizer tokenizer;
IN(InputStream is) {
reader = new BufferedReader(new InputStreamReader(is), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}