作者stimim (qqaa)
看板Prob_Solve
标题Re: [问题]n位整数拿掉m数字得到最大数值
时间Fri Nov 15 13:49:08 2013
:: 我认为这题呢, 要用 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.
: 我反而不懂你这句的意思 QQ
Leon 的作法和我的应该是一样的，
假如现在的字串是
a_0 a_1 a_2 ... a_n
而我们只打算删掉一个数字，
那我们删的一定是第一个 a_i , s.t. a_i < a_{i + 1}
如果不存在这样的 i ，那我们就删 a_n
如果我们要删掉两个数字，可能很容易的证明
a_0 ... a_n
-> b_0 ... b_{n-1}
-> c_0 ... c_{n - 2}
-> 代表做一次上面绿色字的操作。
这麽一来，c_0 ... c_{n-2} 会是最好的结果。
可以再推广到删掉 m 个数字的最好结果就是操作 m 次。
当然，下一次我们不用从 c_0 开始检查，假如上一次被删掉的是 b_i ，
那我们可以知道 b_0 >= b_1 >= b_2 >= ... >= b_{i - 1}, 且 b_j = c_j , j < i
所以下一次只要从 i - 1 开始检查就好了
== PseudoCode ==
Given digis, m
stack := {}
for each digit in digits do
while m > 0 and stack != {} and stack.top < digit do
stack.pop
m := m - 1
end while
stack.push digit
end for
while m > 0 do
stack.pop
end while
answer := 0
exp := 1
while stack != {}
answer := answer + stack.top * exp
stack.pop
exp := exp * 10
end while
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 60.250.111.124
1F：→ jackace:2,1,9 删两个数字取最大 照你这样做是不是会取到2阿 11/19 18:32
2F：推 jackace:看错了 这样是取到9没错 11/19 19:39