题目：乘积最大（无高精度）
思路：
f[i,k]表示前i个数划分为k个部分获得的最大乘积。
num[i,j]表示从i到j的字符拼成的整数。
转移方程：f[i,k]=max{ f[j,k-1]+num[j+1,i] } 。
[1,i]这一段数由j处被分为[1,j]，[j+1,i]两段，其中规定[1,j]这一段在之前的操作中已经被分为k-1段。
注意边界条件：f[j][1]=num[1][j]。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 10
#define maxk 6
#define ll long longint n,K;
int a[maxn+5]= {0};
ll num[maxn+5][maxn+5]={0}; //num(i,j)：i到j的数
ll f[maxn+5][maxn+5]= {0}; //f(i,k)：前i个数被分为k段 void readin() {char str[maxn+5];scanf("%d%d",&n,&K);scanf("%s",str);for(int i=1; i<=n; i++) a[i]=str[i-1]-'0';for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){num[i][j]=num[i][j-1]*10+a[j];}}
}void init(){for(int i=2;i<=n;i++){for(int j=1;j<=K+1;j++){f[i][j]=1;}}for(int j=1;j<=K+1;j++) f[j][1]=num[1][j];
}ll dp() {for(int i=2; i<=n; i++) { //前i个数for(int k=2; k<=K+1&&i>=k; k++) { //被分为k段for(int j=k-1;j<i;j++){ //前k-1次分割的长度 f[i][k]=max(f[i][k],f[j][k-1]*num[j+1][i]);}}}return f[n][K+1];
}int main() {readin();init();ll ans=dp();printf("%lld",ans);return 0;
}