信息学奥赛一本通-1275：【例9.19】乘积最大

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312， 当N=3，K=1时会有以下两种分法：

1）3*12=36

2）31*2=62

这时，符合题目要求的结果是：31*2=62。

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int f[20][20];
int ch[20];
int num[20][20];
/*区间动态规划num[i][j] 预处理，存储从i位到j位的字符组成的数字值
for(int i=1;i<=n;i++){    
for(int j=i;j<=n;j++){       
 num[i][j]=num[i][j-1]*10+ch[j];    
 }}
 f[i][j] 表示前i位数中包含j个乘号的最大乘机 
 
 
 f[i][0]=f[1][1]for(int j=1;j<=m;j++){    
 for(int i=1;i<=n;i++){        
 for(int k=1;k<i;k++){            
    f[i][j]=max(f[i][j],f[k][j-1]*num[k+1][i]);//j个乘号由j-1个乘号推导过来       
  }    
  }}
  */
  int main(){
    cin>>n>>m;
    memset(num,0,sizeof(0));
    memset(f,0,sizeof(0));
    
    for(int i=1;i<=n;i++){
        scanf("%1d",ch+i); //%1d 这里的处理方式每次读一位
    }
    //cout<<ch[1];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            num[i][j]=num[i][j-1]*10+ch[j];
        }
    }
    //cout<<num[1][3];//f[i][j] 表示前i位数中包含j个乘号的最大乘机      f[i][0]=num[1][1]

   for(int i=1;i<=n;i++){
       f[i][0]=num[1][i];
   }

    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            for(int k=1;k<i;k++){
                f[i][j]=max(f[i][j],f[k][j-1]*num[k+1][i]);//j个乘号由j-1个乘号推导过来
            }
        }
    }
    cout<<f[n][m]<<endl;}