网站怎么做出来的,做平台的企业有哪些,中天建设集团有限公司广西分公司,东莞网络科技公司有哪些插入乘号
题目描述
给定一个非负整数#xff0c;用k个乘号将其分割#xff0c;使得乘积最大。 例如#xff1a;在整数12345中插入两个乘号#xff0c;有以下插入法#xff1a; 1*2*345 1*23*45 1*234*5 12*3*45 12*34*5 123*4*5 其中最大值是123*4*5 2460
关于输入
一…插入乘号
题目描述
给定一个非负整数用k个乘号将其分割使得乘积最大。 例如在整数12345中插入两个乘号有以下插入法 1*2*345 1*23*45 1*234*5 12*3*45 12*34*5 123*4*5 其中最大值是123*4*5 2460
关于输入
一行两个非负整数非负整数ss ≦ 10^9和乘号的个数k0 ≦ k s的位数。 输入保证如果按题目要求的乘法操作不会使int发生溢出。
关于输出
一行一个整数即乘积的最大值
例子输入
12345 2
例子输出
2460
解题分析
动态规划能够解决的问题一般可看出解决此问题需要解决的子问题本题中题目给出了两个信息一个是一个非负整数另一个是插入的乘号的数量我们需要想想本题的dp数组应该如何去定义一维还是二维这取决于我们能用几个状态来描述清楚问题。
再来复习一下动态规划的基本思路
动态规划Dynamic Programming简称 DP是一种解决复杂问题的策略主要用于优化问题如求最大值、最小值或者计数问题等。下面是动态规划的基本思路和解决策略
1. **确定状态**在动态规划中状态通常表示为一个或多个变量的组合这些变量能够完全描述一个问题。例如在背包问题中状态可能是当前的重量和价值。
2. **确定状态转移方程**状态转移方程是描述如何从一个状态到另一个状态的规则。在大多数情况下这个规则是基于问题的特性和逻辑来确定的。例如在最长公共子序列问题中如果两个字符相等那么最长公共子序列的长度就是前一个状态的长度加一否则最长公共子序列的长度就是前两个状态中较大的那个。
3. **确定边界条件**边界条件描述了当问题降到最小规模时的解。例如在斐波那契数列问题中边界条件是第一项和第二项分别为1。
4. **计算并存储状态**在动态规划中一般会使用一个表格一维、二维或者更高维度来存储所有的状态。计算顺序通常是从边界条件开始根据状态转移方程逐步计算出所有的状态。
5. **根据存储的状态得到最终结果**在计算出所有的状态后可以根据题目要求从存储的状态中得到最终的结果。
动态规划的关键是理解状态和状态转移方程的概念。一旦理解了这两个概念就可以应用动态规划来解决各种各样的问题。在实际应用中可能需要花费一些时间和思考来确定正确的状态和状态转移方程。
对于我们现在面临的问题可以发现的我们这样去定义dp数组用两个变量来描述清楚问题dp[i][j]其中i表示我们想要处理的数字的前i位而j表示我们想要插入的乘号的数量。
转移方程呢怎么去书写
首先我们需要一个函数去帮助我们去对输入的整数进行分割sub(i,j)表示从i位置到j位置的切割数字。
接下里我们可以把问题化小对于dp[i][j]即在前i个字符内插入j个乘号问题等价于我们从kj位置开始因为要插入j-1个乘号在前k个位置先插入j-1个乘号再把最后一个乘号放在第k个位置然后不断增加k直至k到i-1位置所以我们有,dp[i][j]max(dp[j][j-1]*sub(j,i-1),dp[j1][j-1]*sub(j1,i-1).....dp[i-1][j-1]*sub(i-1,i-1))这个过程可以通过循环实现。
dp代码实现如下
#include iostream
#include cstring
using namespace std;char num[10];
int k;
int dp[10][10]{0};int sub(int i,int j){int ans0;while(ij){ansans*10num[i]-0;i;}return ans;
}int main() {cinnumk;int lenstrlen(num);for(int i1;ilen;i){for(int j0;ji-1 jk;j){if(j0){dp[i][j]sub(0,i-1);}else{for(int kj;ki-1;k){dp[i][j]max(dp[i][j],dp[k][j-1]*sub(k,i-1));}}}}coutdp[len][k]endl;return 0;
}记忆搜索法结合递归代码实现如下
我们定义f(i,j)为在前i个位置插入j个乘号得到的最大值。
#include iostream
#include cstring
using namespace std;char num[10];
int dp[10][10]{0};int sub(int i,int j){int ans0;while(ij){ansans*10num[i]-0;i;}return ans;
}int f(int i,int j){if(dp[i][j]){return dp[i][j];}if(j0){return dp[i][j]sub(0,i-1);}for(int kj;ki-1;k){dp[i][j]max(dp[i][j],f(k,j-1)*sub(k,i-1));}return dp[i][j];
}int main() {int k;cinnumk;int lenstrlen(num);coutf(len,k)endl;return 0;
}
