这道题是很经典的，就在课本上，但第一自己做还是做错了。。。
尴尬了。。。
附上代码，大佬勿喷。

#include<cstdio>
using namespace std;
long long a[11][11],f[11][11];
long long s;
int i,j,k,k1,n;
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    scanf("%d%d",&n,&k1);
    scanf("%lld",&s);
    for(i=n;i>=1;i--)
    {
        a[i][i]=s%10;
        s/=10;
    }
    for(i=2;i<=n;i++)
    {
        for(j=i-1;j>=1;j--)
        {
            a[j][i]=a[j][i-1]*10+a[i][i];
        }
    }
    for(i=1;i<=n;i++)
    {
        f[i][0]=a[1][i];
    }
    for(k=1;k<=k1;k++)
    {
        for(i=k+1;i<=n;i++)
        {
            for(j=k;j<i;j++)
            {
                f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);
            }
        }
    }
    printf("%lld",f[n][k1]);
    return 0;
}

var a,b,c,d,e,f,g,h,n,k:longint;
x:array[1..40,0..6] of string;
s,ss,max:string;
function bigger(s1,s2:string):boolean;
var i,j:integer;
begin
while length(s1)<length(s2) do s1:='0'+s1;
while length(s1)>length(s2) do s2:='0'+s2;
if s1>=s2 then bigger:=true else bigger:=false;
end;
function mul(s1,s2:string):string;
var i,j,k,l1,l2:integer;
x:array[1..256] of byte;
tf:boolean=false;
begin
if (s1='0') or (s2='0') then begin mul:='0'; exit; end;
fillchar(x,sizeof(x),0);
l1:=length(s1); l2:=length(s2);
for i:=1 to l1 do
for j:=1 to l2 do
begin
inc(x[i+j-1],(ord(s1[l1-i+1])-48)*(ord(s2[l2-j+1])-48));
end;
for i:=1 to l1+l2+1 do if x[i]>9 then begin inc(x[i+1],x[i] div 10); x[i]:=x[i] mod 10; end;
mul:='';
for i:=l1+l2+1 downto 1 do if (x[i]<>0) or (tf) then begin mul:=mul+chr(x[i]+48); tf:=true; end;
if not tf then mul:='0';
end;

begin
readln(n,k);
readln(s);
for a:=1 to n do x[a,1]:=copy(s,1,a);
for a:=2 to k+1 do
begin
for b:=a to n-k-1+a do
begin
max:='0';
for c:=1 to b-1 do
begin
ss:=mul(x[c,a-1],copy(s,c+1,b-c));
if bigger(ss,max) then max:=ss;
end;
x[b,a]:=max;
end;
end;
writeln(x[n,k+1]);
end.

uses math;
var
n,m,i,j,k:longint;
f,sum:array[0..40,0..50] of longint;
a:array[0..40] of longint;
ch:char;
begin
readln(n,m);
for i:=1 to n do
begin
read(ch);
a[i]:=ord(ch)-48;
end;
for i:=1 to n do
for j:=i to n do
for k:=i to j do
sum[i,j]:=sum[i,j]*10+a[k];
for i:=1 to n do f[i,0]:=sum[1,i];
for j:=1 to i-1 do//注意这行
for i:=2 to n do
for k:=1 to min(m,i-1) do
f[i,k]:=max(f[i,k],f[j,k-1]*sum[j+1,i]);
writeln(F[n,m]);
end.
这都能过！！！

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
struct bign {
    int a[42], len;
    bign() {
        len=1;
        memset(a,0,sizeof(a));
    }
    bign operator * (const bign &b) {
        bign c;
        for(int i=1; i<=len; i++) {
            for(int j=1; j<=b.len; j++) {
                c.a[i+j-1]+=(a[i]*b.a[j]);
                c.a[i+j]+=c.a[i+j-1]/10;
                c.a[i+j-1]%=10;
            }
        }
        c.len=len+b.len+1;
        c.clean();
        return c;
    }
    bign operator = (const long long int &x) {
        char str[10];
        sprintf(str, "%d", x);
        len=strlen(str);
        for(int i=1; i<=len; i++) {
            a[i]=str[len-i]-'0';
        }
    }
    void clean() {
        while(len>1&&a[len]==0) len--;
    }
    bool operator > (const bign &b) {
        if(len!=b.len) return len>b.len;
        for(int i=len; i>=1; i--) {
            if(a[i] != b.a[i]) return a[i]>b.a[i];
        }
        return 0;
    }
};
ostream& operator << (ostream &out, const bign &x) {
    for(int i=x.len; i>=1; i--)
        printf("%d", x.a[i]);
    return out;
}
bign f[42][7];
char s[42];
int n, k;
bign c(int i, int j) {
    bign r;
    int k=1;
    for(j; j>=i; j--)
        r.a[k++]=s[j-1]-'0';
    r.len=k-1;
    return r;
}
int main() {
    scanf("%d%d%s", &n, &k, s);
    for(int i=1; i<=n; i++) f[i][0]=c(1,i);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=min(i-1,k); j++)
            for(int l=1; l<=i-1; l++) {
                bign t;
                t=c(l+1,i);
                if(f[l][j-1]*t>f[i][j]) f[i][j]=f[l][j-1]*t;
            }
    cout<<f[n][k];
    return 0;
}

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int n,m,a[2001][2001],f[2001][2001];
long long s;
int main ()
{
cin>>n>>m>>s;
for(int i=n;i>=1;i--)
a[i][i]=s%10,s/=10;
for(int i=2;i<=n;i++)
for(int j=1;j<=i-1;j++)
a[i][j]=a[i-1][j]*10+a[i][i];
for(int i=1;i<=n;i++)
f[i][0]=a[i][1];
for(int k=1;k<=m;k++)
for(int i=k+1;i<=n;i++)
for(int j=k;j<i;j++)
f[i][k]=max(f[i][k],f[j][k-1]*a[i][j+1]);
cout<<f[n][m]<<endl;
/*for(int i=1;i<=n;i++)//这是打印后的图形，可以借鉴下。
{
for(int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<f[i][j]<<" ";
cout<<endl;
}*/
return 0;
}

经典DP题，f[i][j] 表示在前i个数字中插入j个乘号时的最大乘积，num[i][j]表示从第i个字符到第j个字符之间的数字，i从0开始
状态转移方程：f[i][j]=max(f[k][j-1]*num[k][i-1]),1<=k<i（注意！num的有效范围从0开始，而f从1开始！怪我咯~）

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
using namespace std;
char str[41];
long long num[41][41],f[41][7];
int n,k,lenstr;
int main(void)
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>str;
    lenstr=strlen(str);
    for(int i=0;i<lenstr;i++)
    {
        num[i][i]=str[i]-'0';
        for(int j=i+1;j<lenstr;j++)
            num[i][j]=num[i][j-1]*10+str[j]-'0';
    }
    for(int i=1;i<=lenstr;i++)
        f[i][0]=num[0][i-1];
    for(int i=1;i<=lenstr;i++)
        for(int j=1;j<=i-1&&j<=k;j++)
            for(int k1=1;k1<i;k1++)
                if(k1>j-1)
                    f[i][j]=max(f[i][j],f[k1][j-1]*num[k1][i-1]);
    cout<<f[lenstr][k];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long a[11][11],f[11][11];
long long s;
int i,j,k,z,n;

int max(int a,int b)
{
if(a>b) return a;
else return b;
}

void in()
{
cin>>n>>z;
cin>>s;
}

void go()
{
for(i=n;i>=1;i--)
{
a[i][i]=s%10;
s/=10;
}

for(i=2;i<=n;i++)
for(j=i-1;j>=1;j--)
a[j][i]=a[j][i-1]*10+a[i][i];

for(i=1;i<=n;i++)
f[i][0]=a[1][i];

for(k=1;k<=z;k++)
for(i=k+1;i<=n;i++)
for(j=k;j<i;j++)
f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);
}

int main()
{
in();
go();
cout<<f[n][z];
return 0;
}

Var
n,k:integer;
num:int64;
s:string;

Procedure dfs(x,y,z:int64);
Var
i,j:integer;
t,q,l:int64;
Begin
t:=0; q:=0; l:=0;
if y=k then
begin
q:=n-z-1; l:=1;
for i:=1 to q do
l:=l*10;
for i:=z+1 to n do
begin
t:=t+(ord(s[i])-48)*l;
l:=l div 10;
end;
x:=x*t;
if num=0 then
num:=x
else
if num<x then
num:=x;
exit;
end;
for i:=z+1 to n do
begin
q:=i-(z+1); l:=1;
for j:=1 to q do
l:=l*10;
for j:=z+1 to i do
begin
t:=t+(ord(s[j])-48)*l;
l:=l div 10;
end;
dfs(x*t,y+1,i);
t:=0;
end;
End;

Begin
readln(n,k);
readln(s);
num:=0;
dfs(1,0,0);
writeln(num);
readln;
End.
等下，，，为啥这题正解上写着DP，，我这个DFS还是秒过。。。。这数据水到爆！！！！

简单的DP。

var
  s:string[40];
  a:array[1..40, 1..40] of longint;
  f:array[1..40, 0..6] of qword;
  n, k, i, j, r:longint;
begin
  readln(n, k);
  read(s);
  for i:=1 to n do
    for j:=i to n do val(copy(s, i, j-i+1), a[i, j], r);
  fillchar(f, sizeof(f), 0);
  for i:=1 to n do f[i, 0]:=a[1, i];
  for i:=1 to n do
    for j:=1 to i-1 do
      for r:=j to i-1 do if f[r, j-1]*a[r+1, i]>f[i, j] then f[i, j]:=f[r, j-1]*a[r+1, i];
  write(f[n, k])
end.

乖乖用DP。

var
  s:string[40];
  a:array[1..40, 1..40] of longint;
  f:array[1..40, 0..6] of qword;
  n, k, i, j, r:longint;
begin
  readln(n, k);
  read(s);
  for i:=1 to n do
    for j:=i to n do val(copy(s, i, j-i+1), a[i, j], r);
  fillchar(f, sizeof(f), 0);
  for i:=1 to n do f[i, 0]:=a[1, i];
  for i:=1 to n do
    for j:=1 to i-1 do
      for r:=j to i-1 do if f[r, j-1]*a[r+1, i]>f[i, j] then f[i, j]:=f[r, j-1]*a[r+1, i];
  write(f[n, k])
end.

数据好水
这么多dp发个dfs
var
s:string;
k,n:longint;
max:int64;
procedure dfs(a:int64;b,c:longint);
var
i,j:longint;
m:int64;
begin
m:=0;
if b=0 then
begin
for i:=c to n do
begin
m:=m+ord(s[i])-ord('0');
m:=m*10;
end;
a:=a*m div 10;
if a>max then max:=a;
exit;
end;
for i:=c to n-b do
begin
m:=m+ord(s[i])-ord('0');
dfs(a*m,b-1,i+1);
m:=m*10;
end;
end;
begin
max:=-maxlongint;
readln(n,k);
readln(s);
dfs(1,k,1);
writeln(max);
end.

type arr=array [0..50] of longint;
var
a:arr;
b,f:array [0..50,0..50] of arr;
ch:char;
i,j,k,n,p:longint;
function max(a,b:arr):arr;
var i:longint;
begin
if (a[0]>b[0]) then exit(a);
if (a[0]<b[0]) then exit(b);
for i:=a[0] downto 1 do
begin
if (a[i]>b[i]) then exit(a);
if (a[i]<b[i]) then exit(b);
end;
exit(a);
end;
function cheng(a,b:arr):arr;
var i,j,x:longint;
c:arr;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
begin
x:=0;
for j:=1 to b[0] do
begin
x:=x+a[i]*b[j]+c[i+j-1];
c[i+j-1]:=x mod 10;
x:=x div 10;
end;
c[i+b[0]]:=x;
end;
c[0]:=a[0]+b[0];
while (c[0]<>1) and (c[c[0]]=0) do dec(c[0]);
exit(c);
end;
begin
readln(n,p);
for i:=1 to n do begin read(ch); a[i]:=ord(ch)-48; end;
for i:=1 to n do
for j:=i to n do
begin
for k:=b[i,j-1,0] downto 1 do b[i,j,k+1]:=b[i,j-1,k];
b[i,j,1]:=a[j]; b[i,j,0]:=b[i,j-1,0]+1;
while (b[i,j,b[i,j,0]]=0) and (b[i,j,0]<>1) do dec(b[i,j,0]);
end;
for i:=1 to n do f[0,i]:=b[1,i];
for i:=1 to p do
for j:=1 to n-1 do
for k:=j+1 to n do
f[i,k]:=max(f[i,k],cheng(f[i-1,j],b[j+1,k]));
for i:=f[p,n,0] downto 1 do write(f[p,n,i]);
end.

n最大才20，背包穷举能够

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n, k, a[50], c[50];
char s[50];
long long ans;

int main()
{
scanf("%d%d", &n, &k);
scanf("%s", s);
for(int i = 0; i < n; i++)a[i] = s[i]-'0';
for(int s = 0; s < (1<<n); s++){
int cnt = 1;
memset(c, 0, sizeof(c));
c[k+1] = n-1;c[0] = -1;
for(int j = 0; j < n-1; j++)if(s&(1<<j))c[cnt++] = j;
if(cnt-1 != k)continue;
long long r = 1, v;
for(int i = 1; i <= cnt; i++){
v = 0;
for(int l = c[i-1]+1; l <= c[i]; l++)v=v*10 + a[l];
r *= v;
}
ans = max(r, ans);
}
printf("%lld", ans);
return 0;
}

#include <iostream>

using namespace std;

int main() {
    char str[41];
    long long s[41][41], f[41][41] = {0};
    int x = 1;
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> str[i];
        s[i][i] = str[i] - '0';
    }
    for (int p = 1; p <= n; ++p) {
        for (int i = 1; i <= n, i + p <= n; ++i) {
            if (i + p > n)break;
            s[i][i + p] = s[i][i + p - 1] * 10 + (str[i + p] - '0');
        }
    }
    for (int i = 1; i <= n; ++i) {
        f[i][0] = s[1][i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= min(k, i - 1); ++j) {
            for (int k = j; k < i; k++) {
                f[i][j] = max(f[i][j], f[k][j - 1] * s[k + 1][i]);
            }
        }

    }
    cout << f[n][k] << endl;

    return 0;
}

记录信息
评测状态 Accepted
题目 P1347 乘积最大
递交时间 2015-08-31 09:09:04
代码语言 C++
评测机 VijosEx
消耗时间 38 ms
消耗内存 852 KiB
评测时间 2015-08-31 09:09:05
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:35:30: warning: unknown conversion type character 'l' in format [-Wformat=]
printf("%lld",dp[1][n][k]);
^
foo.cpp:35:30: warning: too many arguments for format [-Wformat-extra-args]
测试数据 #0: Accepted, time = 1 ms, mem = 852 KiB, score = 23
测试数据 #1: Accepted, time = 0 ms, mem = 852 KiB, score = 27
测试数据 #2: Accepted, time = 22 ms, mem = 848 KiB, score = 23
测试数据 #3: Accepted, time = 15 ms, mem = 852 KiB, score = 27
Accepted, time = 38 ms, mem = 852 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
using namespace std;
long long num[45][45],dp[45][45][20];
char s[150];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s);

for(int dist=0;dist<n;dist++)
for(int i=1;i+dist<=n;i++)
num[i][i+dist]=num[i][dist+i-1]*10+s[dist+i-1]-'0';
for(int i=0;i<n;i++)
for(int j=1;j+i<=n;j++)
dp[j][i+j][0]=num[j][i+j];
for(int i=1;i<=k;i++)
{
for(int j=i-1;j<n;j++)
{
for(int o=1;o+j<=n;o++)
{
for(int pos=o;pos<j+o;pos++)
{
dp[o][j+o][i]=max(dp[o][o+j][i],num[o][pos]*dp[pos+1][o+j][i-1]);

}
for(int pos=o;pos<j+o;pos++)
{
dp[o][j+o][i]=max(dp[o][o+j][i],dp[o][pos][i-1]*num[pos+1][o+j]);

}
}
}
}
printf("%lld",dp[1][n][k]);
}

var n,t:longint;
s1:string;
f:array[1..40,0..6] of string;
sum:array[1..40,1..40] of string;
function mul(n1,n2:string):string;
var lena,lenb,lenc,i,j:integer;
x:longint;
a,b,c:array[1..200] of integer;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
lena:=length(n1);
lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-48;
for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-48;
for i:=1 to lena do
begin
x:=0;
for j:=1 to lenb do
begin
x:=x div 10+c[i+j-1]+a[i]*b[j];
c[i+j-1]:=x mod 10;
end;
c[i+j]:=x div 10;
end;
lenc:=i+j;
while (lenc>1) and (c[lenc]=0) do dec(lenc);
mul:='';
for i:=lenc downto 1 do mul:=mul+chr(c[i]+48);
end;
function max(c,s:string):string;
var lc,ls,i:integer;
begin
lc:=length(c);
ls:=length(s);
if lc>ls then exit(c);
if ls>lc then exit(s);
for i:=1 to ls do
begin
if c[i]>s[i] then exit(c);
if s[i]>c[i] then exit(s);
end;
exit(c);
end;
procedure dynamic;
var i,j,k:integer;
begin
readln(n,t);
readln(s1);
for i:=1 to n do for j:=0 to t do f[i,j]:='';
for i:=1 to n do
for j:=i to n do sum[i,j]:=copy(s1,i,j-i+1);
for i:=1 to n do f[i,0]:=sum[1,i];
for k:=1 to t do
for i:=k+1 to n do
for j:=k to i-1 do f[i,k]:=max(f[i,k],mul(f[j,k-1],sum[j+1,i]));
writeln(f[n,t]);
end;
begin
dynamic;
end.

思路：
1.果断高精度。
2.开两个数组（sum[i,j])(f[i,j])。sum[i,j]记录字符串的第i位到第j位所组成的自然数。f[i,j]记录字符串的前i位中添加j个乘号的最大值。DP的方程为：f[i,k]:=max(f[i,k],f[j,k-1]*sum[j+1,i])。
for k:=1 to t do
for i:=k+1 to n do
for j:=k to i-1 do f[i,k]:=max(f[i,k],mul(f[j,k-1],sum[j+1,i]));
如果还是不明白，可以手刃算算，就知道方法了。
手刃：
位数（自然数）
1 12 123 1231

乘号 -------------------------------------------

0 | 1 12 123 1231
1 | 无 2 36 372
2 | 无 无 6 62

40位6个乘号果断高精度。
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[43][7][47];
bool visited[43][7];
char str[43];
int numSize;
int cheng;
void mul(int res[], int x[], int y[]){
int i,j;
for (i = 0; i < 47; i++){
for (j = 0; j < 47; j++){
res[i + j] += x[i] * y[j];
}
}
for (i = 0; i<47; i++){
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
}
bool better(int res[], int ans[]){
int i;
for (i = 46; i >= 0; i--){
if (res[i]>ans[i])return true;
if (res[i] < ans[i])return false;
}
return false;
}
void init(int from, int ge){
visited[from][ge] = true;
int i;
if (ge == 0){

for (i = 0; i < numSize - from; i++){
a[from][ge][i] = str[numSize-1-i] - '0';
}
}
else{
int best[47];
int now[47];
int res[99];
memset(best, 0, sizeof(best));
int j;
for (i = from; i < numSize - ge; i++){
memset(now, 0, sizeof(now));
for (j = i; j >= from; j--){
now[i - j] = str[j] - '0';
}
if (!visited[i+1][ge-1]){
init(i + 1, ge - 1);
}
memset(res, 0, sizeof(res));
mul(res, now, a[i + 1][ge-1]);
if (better(res, best)){
for (j = 0; j < 47; j++)
best[j] = res[j];
}
}
for (i = 0; i < 47; i++)
a[from][ge][i] = best[i];
}
}
int main(){
freopen("in.txt", "r", stdin);
cin >> numSize >> cheng;
cin >> str;
memset(a, 0, sizeof(a));
memset(visited, 0, sizeof(visited));
init(0,cheng);
int i;
int *ans = a[0][cheng];
for (i = 46; ans[i] == 0; i--);
while (i >= 0){
cout << ans[i--];
}
return 0;
}

#include<stdio.h>
#include<stdlib.h>
int exchange(char *string)
{
int i=1;
int total=0;
while(string[i]!='\0')
{
total=total*10+string[i]-'0';
i++;
}
return total;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a,b,c;
char number[45];
scanf("%s",number);
int record[45][10]={0};//第一维为在多长的数字串里加，第二维为加几个乘号
for(a=2;a<=n;a++)
{
int max=-1;
for(b=1;b<=a-1;b++)
{
char string1[45],string2[45];
int x,y;
for(x=0,y=1;x<=b-1;x++,y++)
string1[y]=number[x];
string1[y]='\0';
for(x=b,y=1;x<=a-1;x++,y++)
string2[y]=number[x];
string2[y]='\0';
int use1,use2;
use1=exchange(string1);
use2=exchange(string2);
if(use1*use2>max)
max=use1*use2;
}
record[a][1]=max;
}
for(a=2;a<=m;a++)//加多少个乘号
for(b=2;b<=n;b++)//多长的数字串里加
{
int max=-1;
for(c=a;c<=b-1;c++)//数字串循环
{
char use[45];
int x,y;
int cal;
int compare;
for(x=c,y=1;x<=b-1;x++,y++)
use[y]=number[x];
use[y]='\0';
cal=exchange(use);
compare=record[c][a-1]*cal;
if(compare>max)
max=compare;
}
record[b][a]=max;
}
printf("%d",record[n][m]);
return 0;
}

我无语……
用高精度，WA0
用int64，AC……

DP
令f[i,j]表示从1到i,分为 j份的最大值。
f[i,j]=max(f[i1,j-1]*num[i1+1,i]) 0<i1<i