PuzzleUp 2009 (12) Ascending Letters - 拼圖

Table of Contents

首頁:http://www.puzzleup.com/2009/?home
時限:2009/10/08(四)19:00~10/14(二)18:59
答案可上傳次,但每改1次扣20(基本分為100分)
在比賽期間內可隨時回答,但只有在時限內回答者有額外加分

◆Ascending Letters

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

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

以下舉兩個7個字母(A、B、C、D、E、F、G)的例子:

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

BGEDFCA ←方向


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

方向→ DBCAGEF


--

All Comments

Annie avatarAnnie2009-10-08
這次的題目真是麻煩=.="
Rachel avatarRachel2009-10-11
這竟然是 Longest Increasing Subsequence...@_@|||||
Regina avatarRegina2009-10-15
太好了 樓上偷偷告訴我答案...我懶得算了-.-"
Kelly avatarKelly2009-10-16
帕索好自私喲!o(〒﹏〒)o
Gilbert avatarGilbert2009-10-18
啊, 我只是把這個題目重講一遍而已 XD
帕索大果然厲害, 這樣就可以悟出答案 XDDDD
Isla avatarIsla2009-10-21
我對這題的解讀是:讓你任意排列26字母,如何使得最長遞升
字串最小?
Joseph avatarJoseph2009-10-24
所以LIS的演算法應該是不相關的
Ula avatarUla2009-10-28
我的答案反而是去找一個特定結構,盡量讓遞升狀況最少化
Joseph avatarJoseph2009-10-29
剛用程式驗證過了,程式網路上就有 http://ppt.cc/jVCC
Rosalind avatarRosalind2009-11-02
如果我的想法沒錯的話,字母數=26這點很微妙 :p
Kyle avatarKyle2009-11-06
我發現一件很奇妙的事情!!
Jessica avatarJessica2009-11-11
這題在離散數學中很有名.但證明從來沒看懂過(攤)
Emma avatarEmma2009-11-15
幹嘛要出這種題目啊◢▆▅▄▃崩╰(〒皿〒)╯潰▃▄▅▇◣
Faithe avatarFaithe2009-11-17
PuzzleUp才出到第24題啊...知道其他題目的作法orz
Connor avatarConnor2009-11-22
好想
Suhail Hany avatarSuhail Hany2009-11-26
我想把 NumberGame轉到MATH版給大家討論.啪所同意嗎
Jacob avatarJacob2009-11-30
嗯,OK呀....
Linda avatarLinda2009-12-04
感覺跟鴿籠原理有關
Frederic avatarFrederic2009-12-07
數學板有討論到這一篇 可是當時沒把編號記下
Mary avatarMary2009-12-11
現在回頭去找 卻找不到了...好像是這兩個月內的文章
Emily avatarEmily2009-12-12
這比賽我好早就放棄了(崩潰)
Wallis avatarWallis2009-12-16
u大說得沒錯 (Math) #1ADqDBUY 鴿籠原理真好用
George avatarGeorge2009-12-20
看不懂證明+1 不過隱約可以感受到它的原理.....
Zenobia avatarZenobia2009-12-22
http://tinyurl.com/ylqqdd 謝教授的網頁
Eartha avatarEartha2009-12-23
其中1.4. 十人中之高矮次序有證明,還蠻好懂的
Franklin avatarFranklin2009-12-26
不過其中的ain <= ain+1 應該是ain >= ain+1
Yedda avatarYedda2009-12-27
那個網頁我之前有找到 也是看不懂啊>"<
Franklin avatarFranklin2009-12-28
謝教授寫得沒錯 應該是ain <= ain+1
Frederica avatarFrederica2010-01-02
噢...如果你說的是最後1行的那一個 那的確是筆誤
Madame avatarMadame2010-01-05
a大提到26,26是唯一在平方數(25)和立方數(27)之間的數字
Bennie avatarBennie2010-01-08
上次那個硬幣問題 轉到數學板去 馬上被秒殺了
Ursula avatarUrsula2010-01-09
結果我們還跑了半天的程式 算出來還是錯的答案
只能說 我們太嫩了
Andrew avatarAndrew2010-01-11
"我們"應該不包括帕索大...帕索都裝嫩>"<
Candice avatarCandice2010-01-14
咦?u大你硬幣問題也算出最佳解了吧,有錯嗎?@@a