作者puzzlez (渴望一份好工作)
看板puzzle
标题[中译] PuzzleUp 2009 (12) Ascending Letters
时间Wed Oct 7 19:28:09 2009
首页：
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)
1F：→ puzzlez:这次的题目真是麻烦=.=" 10/07 19:41
2F：推 LPH66:这竟然是 Longest Increasing Subsequence...@_@||||| 10/07 22:51
3F：→ puzzlez:太好了 楼上偷偷告诉我答案...我懒得算了-.-" 10/07 23:34
4F：推 FACE90006:帕索好自私哟!o(〒﹏〒)o 10/07 23:46
5F：推 LPH66:啊, 我只是把这个题目重讲一遍而已 XD 10/08 01:58
6F：→ LPH66:帕索大果然厉害, 这样就可以悟出答案 XDDDD 10/08 01:58
7F：推 ars1an:我对这题的解读是：让你任意排列26字母，如何使得最长递升 10/08 04:49
8F：→ ars1an:字串最小？ 10/08 04:49
9F：→ ars1an:所以LIS的演算法应该是不相关的 10/08 04:50
10F：→ ars1an:我的答案反而是去找一个特定结构，尽量让递升状况最少化 10/08 04:52
12F：推 ars1an:如果我的想法没错的话，字母数=26这点很微妙 :p 10/08 05:08
13F：推 stimim:我发现一件很奇妙的事情!! 10/08 12:31
14F：推 coolbetter33:这题在离散数学中很有名.但证明从来没看懂过(摊) 10/08 12:45
15F：→ puzzlez:干嘛要出这种题目啊◢▆▅▄▃崩╰(〒皿〒)╯溃▃▄▅▇◣ 10/08 13:02
16F：推 stimim:PuzzleUp才出到第24题啊...知道其他题目的作法orz 10/08 13:21
17F：→ stimim: 好想 10/08 13:22
18F：→ coolbetter33:我想把 NumberGame转到MATH版给大家讨论.啪所同意吗 10/08 13:24
19F：→ puzzlez:嗯，OK呀.... 10/08 13:56
20F：推 utomaya:感觉跟鸽笼原理有关 10/08 19:08
21F：→ utomaya:数学板有讨论到这一篇 可是当时没把编号记下 10/08 19:10
22F：→ utomaya:现在回头去找 却找不到了...好像是这两个月内的文章 10/08 19:11
23F：推 werul:这比赛我好早就放弃了(崩溃) 10/08 19:19
24F：推 ars1an:u大说得没错 (Math) #1ADqDBUY 鸽笼原理真好用 10/09 03:13
25F：→ puzzlez:看不懂证明+1 不过隐约可以感受到它的原理..... 10/09 10:43
27F：→ turing:其中1.4. 十人中之高矮次序有证明，还蛮好懂的 10/09 12:41
28F：→ turing:不过其中的ain <= ain+1 应该是ain >= ain+1 10/09 12:43
29F：→ puzzlez:那个网页我之前有找到 也是看不懂啊>"< 10/09 15:54
30F：推 utomaya:谢教授写得没错 应该是ain <= ain+1 10/09 17:44
31F：→ utomaya:噢...如果你说的是最後1行的那一个 那的确是笔误 10/09 17:49
32F：推 turing:a大提到26，26是唯一在平方数(25)和立方数(27)之间的数字 10/09 18:10
33F：推 utomaya:上次那个硬币问题 转到数学板去 马上被秒杀了 10/09 18:25
34F：→ utomaya:结果我们还跑了半天的程式 算出来还是错的答案 10/09 18:26
35F：→ utomaya:只能说 我们太嫩了 10/09 18:26
36F：推 FACE90006:"我们"应该不包括帕索大...帕索都装嫩>"< 10/09 19:55
37F：推 ars1an:咦？u大你硬币问题也算出最佳解了吧，有错吗？@@a 10/09 20:16