[中譯] PuzzleUp 2009 (12) Ascending Letters

[puzzlez (渴望一份好工作)]

首頁：http://www.puzzleup.com/2009/?home
時限：2009/10/08（四）19:00～10/14（二）18:59
      答案可上傳５次，但每改１次扣２０分（基本分為１００分）      
      在比賽期間內可隨時回答，但只有在時限內回答者有額外加分      

◆Ascending Letters

將 a～z 26個英文字母的次序打亂，重新排列出一條字串。然後再由前往後或由後往前，
從其中一個字母開始，挑出接下來字母次序遞升者，形成另一個新字串。就這樣反覆嘗試
，挑出其中最長的字串。

請問這條次序遞升且最長的新字串，最小的長度是多少？

以下舉兩個7個字母（A、B、C、D、E、F、G）的例子：

若重新排列過後的字串為：BGEDFCA
那麼其中次序遞升字串，最長者為 GEDCA（方向是由後往前找，從字母A開始）

                        BGEDFCA  ←方向


若重新排列過後的字串為：DBCAGEF
那麼其中次序遞升字串，最長者為 BCEF（方向是由前往後找，從字母B開始）

               方向→   DBCAGEF


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.247.146
※ 編輯: puzzlez         來自: 123.194.247.146      (10/07 19:37)
→ puzzlez:這次的題目真是麻煩=.="
推 LPH66:這竟然是 Longest Increasing Subsequence...@_@|||||
→ puzzlez:太好了 樓上偷偷告訴我答案...我懶得算了-.-"
推 FACE90006:帕索好自私喲!o(〒﹏〒)o
推 LPH66:啊, 我只是把這個題目重講一遍而已 XD
→ LPH66:帕索大果然厲害, 這樣就可以悟出答案 XDDDD
推 ars1an:我對這題的解讀是：讓你任意排列26字母，如何使得最長遞升
→ ars1an:字串最小？
→ ars1an:所以LIS的演算法應該是不相關的
→ ars1an:我的答案反而是去找一個特定結構，盡量讓遞升狀況最少化
推 ars1an:剛用程式驗證過了，程式網路上就有 http://ppt.cc/jVCC
推 ars1an:如果我的想法沒錯的話，字母數=26這點很微妙 :p
推 stimim:我發現一件很奇妙的事情!!
推 coolbetter33:這題在離散數學中很有名.但證明從來沒看懂過(攤)
→ puzzlez:幹嘛要出這種題目啊◢▆▅▄▃崩╰(〒皿〒)╯潰▃▄▅▇◣
推 stimim:PuzzleUp才出到第24題啊...知道其他題目的作法orz
→ stimim:                      好想
→ coolbetter33:我想把 NumberGame轉到MATH版給大家討論.啪所同意嗎
→ puzzlez:嗯，OK呀....
推 utomaya:感覺跟鴿籠原理有關
→ utomaya:數學板有討論到這一篇 可是當時沒把編號記下
→ utomaya:現在回頭去找 卻找不到了...好像是這兩個月內的文章
推 werul:這比賽我好早就放棄了(崩潰)
推 ars1an:u大說得沒錯 (Math) #1ADqDBUY 鴿籠原理真好用
→ puzzlez:看不懂證明+1 不過隱約可以感受到它的原理.....
推 turing:http://tinyurl.com/ylqqdd 謝教授的網頁
→ turing:其中1.4. 十人中之高矮次序有證明，還蠻好懂的
→ turing:不過其中的ain <= ain+1 應該是ain >= ain+1
→ puzzlez:那個網頁我之前有找到 也是看不懂啊>"<
推 utomaya:謝教授寫得沒錯 應該是ain <= ain+1
→ utomaya:噢...如果你說的是最後1行的那一個 那的確是筆誤
推 turing:a大提到26，26是唯一在平方數(25)和立方數(27)之間的數字
推 utomaya:上次那個硬幣問題 轉到數學板去 馬上被秒殺了
→ utomaya:結果我們還跑了半天的程式 算出來還是錯的答案
→ utomaya:只能說 我們太嫩了
推 FACE90006:"我們"應該不包括帕索大...帕索都裝嫩>"<
推 ars1an:咦？u大你硬幣問題也算出最佳解了吧，有錯嗎？@@a