Re: [問題]n位整數拿掉m數字得到最大數值
看板Prob_Solve (計算數學 Problem Solving)作者stimim (qqaa)時間11年前 (2013/11/15 13:49)推噓1(1推 0噓 1→)留言2則, 1人參與討論串4/5 (看更多)
:: 我認為這題呢, 要用 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
→
11/19 18:32, , 1F
11/19 18:32, 1F
推
11/19 19:39, , 2F
11/19 19:39, 2F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
