作者cutekid (可爱小孩子)
看板Prob_Solve
标题[问题] Maximum Product
时间Thu Sep 8 17:39:26 2016
给定一个数字 N (由 1 ~ 9组成)
其中插入 K 个乘号，使最後相乘的值要最大
举例:
N = 746589, K = 2, 最大值 = 7465 x 8 x 9
N = 1111114, K = 3, 最大值 = 11 x 11 x 11 x 4
请问这题除了 C(长度 - 1,K) 暴力搜寻
还有什麽比较好的算法吗
谢谢 ^_^
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 210.61.233.210
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1473327569.A.C7C.html
1F：推 FRAXIS: 有负数吗? 09/09 08:46
没有负数喔~~
2F：→ FRAXIS: 而且这看起来就可以 DP 吧.. 09/09 08:47
是喔??怎麽个 DP 法(因为 N 的长度可能大於 10)，可以提示一下吗^^
※ 编辑: cutekid (210.61.233.210), 09/09/2016 13:20:04