当前位置:首页 > NOIP > 正文

信息学奥赛一本通-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;}


更新时间 2019-03-25

有话要说...