简化问题:
给原数字之前添加一个"1 *",乘号不计入数量,对答案无影响。
例如:"1231"可以变成"(1*)1231"。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
表示状态
dp[i][j] = max num(最后一个乘号之前的最大乘积)
* i:此时在第i个数的前面添了一个乘号
* j:用了j个乘号
例1:"(1*)12*31":
* dp[2][1] = 12 (数位从0开始从左向右编号)
例2:"(1*)1231"
* dp[3][2] = 12*3 = 36
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
找出答案
max dp[i][t] * cal_sec(i,n-1)
cal_sec(x,y)将数字串中[x,y]这个区间的字符串转化为数字
> 例如:设n=4,t=1.
>
> > 此时为"(1*)1231"
> > 则此时这种方案的乘积为dp[2][1] "31" = 12*31
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
转移方程
dp[i][j] = max dp[k][j-1] * cal_sec(k,i-1)
在前面的某一段乘积后面再续上一串数字,达到第i位,用了j个乘号。
前面的某一段乘积:枚举最后一个乘号在第k个数字之前,用了j-1个乘号。
要续的数字:从第k位到i-1位 = cal_sec(k,i-1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
边界条件
初始时用了0个乘号,但乘积为1。
例如:"(1*)1231".
特判:如果输入的数字就是0,则直接返回0.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
AC代码