20-最大k乘积问题

/*
　　　　　　　　　　　　最大k乘积问题
题目内容：

设I是一个n位十进制整数.如果将I划分为k段,则可得到k个整数.这k个整数的乘积称为I的一个k乘积.试设计一个算法,对于给定的I和k ,求出I的最大k乘积.
Input
输入的第1行中有2个正整数n和k.正整数n是序列的长度;正整数k是分割的段数.接下来的一行中是一个n位十进制整数.（n<=10）
Output
输出计算结果，第1行中的数是计算出的最大k乘积.
n位十进制整数.（n<=10）

输入描述

输入的第1行中有2个正整数n和k.正整数n是序列的长度;正整数k是分割的段数.接下来的一行中是一个

输出描述

输出计算结果，第1行中的数是计算出的最大k乘积.

输入样例

2 1
15

输出样例

15
*/
//思路：构造dp[i][k]表示从1到i位数分成k段的最大值，m[i][j]表示一个整数的第i位到j位构成的整数。
//递推关系： dp[i][k] = max(dp[i][k], dp[j][k - 1] * m[j+1][i], 1<=j<i; j表示分割的位置,枚举j,可以求得最大dp[i][k]

1.递归

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[15][15];
int m[15][15];

int fun(int i, int k){   //递归求解，表示返回从1到i位数分成k份相乘的最大数
   if(k == 1)
       return dp[i][k] = m[1][i];
   if(dp[i][k] != 0)
       return dp[i][k];
   for(int j = 1; j < i; j++){
       dp[i][k] = max(dp[i][k], fun(j, k - 1) * m[j + 1][i]);
   }
   return dp[i][k];
}

int main(){
   int n, k, s;
   while(~scanf("%d%d", &n, &k)){
       memset(m, 0, sizeof(m));
       memset(dp, 0, sizeof(dp));
       scanf("%d", &s);
       int S = 1;
       for(int i = 1; i <= n; i++)
           S *= 10;
       //初始话m数组，将s的i到j位数存在里面
       for(int i = 1; i <= n; i++){
           m[i][n] = s % S;
           S /= 10;
           for(int j = n - 1; j >= i; j--){
               m[i][j] = m[i][j + 1] / 10;
//               cout << m[i][j] << " ";
           }
//           cout << endl;
       }
       cout << fun(n, k);
   }
   return 0;
}

2.递推：

#include <iostream>
using namespace std;
int dp[100][100];
int m[100][100];

int main(){
   int n, k, a;
   cin >> n >> k >> a;
   if(k == 1){
       cout << a;
       return 1;
   }
   int b = 1, q = 1;
   for(int i = n; i >= 1; i--){
       int p = 10;
       b = a / q;
       q *= 10;
//       cout << b << endl;
       for(int j = i; j >= 1; j--){
           m[j][i] = b % p;
           p *= 10;
//           cout << m[j][i] << " ";
       }
   }
//   dp[1][1] = a;
   for(int i = 1; i <= n; i++){       //枚举前n个数字
       for(int j = 0; j <= i; j++){   //枚举乘号的个数
           if(j == 0){
               dp[i][j] = m[1][i];
               continue;
           }
           for(int n = 1; n <= i; n++)//枚举乘号的位置
               dp[i][j] = max(dp[i][j], dp[n][j-1]*m[k+1][i]);
       }
   }
   cout << dp[n][k];
   return 0;
}

巴特西

20-最大k乘积问题

最新文章

热门文章