作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题]n位整数拿掉m数字得到最大数值
时间Fri Nov 15 11:10:06 2013
※ 引述《PATRICKSTARS (PatrickStar)》之铭言：
: Given an integer (not necessary a decimal number) with n digits, we want to
: remove m (<=n) digits from this number such that the resulting number is as
: large as possible. Design an O(n) time algorithm to solve it.
: 可以提示如何下手吗?
嗯, 我看了一下.
Range Minimum Query (RMQ) 似乎不太对啊.
举个简单的例子好了(有人已经点出来了)
2-3-4-5-1-1, remove 2 digits
RMQ 应该会得到 2-3-4-5,
但这题的最佳解应该是 4-5-1-1.
(希望我没有误解你的意思)
我认为这题呢, 要用 increasing sequence 的观念去看.
从简单的 case 出发:
1-2-3-4, increasing sequence, so everytime we remove,
we start from begining.
4-3-2-1, decreasing sequence, then we remove from back.
Thus, when we work on it,
we start from making the leading sequence as a decreasing sequence,
then remove the inflection point.
--
赵客缦胡缨，吾钩霜雪明。银鞍照白马，飒沓如流星。
十步杀一人，千里不留行。是了拂衣去，深藏身与名。
闲过信陵饮，脱剑膝前横。将炙啖朱亥，持觞劝侯赢。
三杯吐然诺，五岳倒为轻。眼花耳热後，意气素霓生。
就赵挥金锤，邯郸先震惊。千秋二壮士，烜赫大梁城。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 68.181.4.115