这题的考点涉及了高精度（乘法）模拟和动态规划。
状态设计：dp[i][j]这个结构体表示在i个数中间放j个乘号的最大结果。
转移方程：我们需要枚举最后一个乘号是在哪里放的，直接计算一下最后一个乘号之前的数字加入k-1个乘号时的最大值，再乘以最后一个乘号之后的数字。
高精在这题有这几个应用：
1.取数 将没有乘号分隔的连续的数字变成一个数，进行运算
2.比较 没有比较哪来的最大值
3.乘法 将乘号两边取到的数乘起来
#include<bits/stdc++.h> using namespace std; const int N=100; int n,K,a[N]; string s; struct node { int len,ans[N]; }dp[N/10][N]; node cal(node x,int l,int r) { node answ,y; memset(answ.ans,0,sizeof(answ.ans)); memset(y.ans,0,sizeof(y.ans)); y.len=r-l+1; for(int i=r;i>=l;i--) y.ans[r-i+1]=a[i]; int len1=x.len,len2=y.len,len; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) answ.ans[i+j-1]+=x.ans[i]*y.ans[j]; len=len1+len2-1; for(int i=1;i<=len;i++) { answ.ans[i+1]+=answ.ans[i]/10; answ.ans[i]%=10; } if(answ.ans[len+1]) len++; answ.len=len; return answ; } node cmp(node x,node y) { int lenx=x.len,leny=y.len; if(lenx<leny) return y; if(lenx>leny) return x; for(int i=lenx;i>=1;i--) { if(x.ans[i]>y.ans[i]) return x; if(x.ans[i]<y.ans[i]) return y; } return x; } int main() { scanf("%d%d",&n,&K); cin>>s; for(int i=1;i<=n;i++) a[i]=s[i-1]-‘0‘; for(int i=1;i<=n;i++) for(int j=i;j>=0;j--) dp[0][i].ans[++dp[0][i].len]=a[j]; for(int i=2;i<=n;i++) for(int k=1;k<=min(K,i-1);k++) for(int j=k;j<i;j++) dp[k][i]=cmp(dp[k][i],cal(dp[k-1][j],j+1,i)); for(int i=dp[K][n].len;i>=1;i--) printf("%d",dp[K][n].ans[i]); return 0; }
原文：https://www.cnblogs.com/Siv0106/p/11722293.html