|
留言
|
|
主題： |
2001的題目的一些問題 |
|
留言人： |
無 |
| 留言日期： | 2003/10/22 上午 10:09:11 |
| 留言IP： | |
| 留言內容： | 請問有人知道2001年國中組題目E 撿石頭 的解法嗎？ 因為那題的情況很多ㄟ, 可能前面有1個大的可以撿, 但是如果捨去不撿, 而使後面能夠撿更多的話, 那情況就多了, 還是說主辦單位的輸入資料不會那麼複雜？ |
|
目前回應文章
|
| 回覆人 | 主題 | 回覆日期 |
| 火星人刑事 | Re:2001的題目的一些問題: | 2003/10/22 下午 08:48:47 |
| 火星人刑事 | Re:2001的題目的一些問題: | 2003/10/22 下午 10:13:37 |
| 無 | Re:2001的題目的一些問題: | 2003/10/23 上午 08:53:35 |
| 我 | 該是時候了: | 2003/10/24 下午 10:19:18 |
| aaaa | Re:2001的題目的一些問題: | 2022/12/8 下午 10:53:43 |
| bbb | Re:2001的題目的一些問題: | 2022/12/8 下午 10:54:50 |
| ggg | Re:2001的題目的一些問題: | 2022/12/8 下午 10:56:11 |
| aaaaaaaa | Re:2001的題目的一些問題: | 2022/12/8 下午 10:57:39 |
| ddd | Re:2001的題目的一些問題: | 2022/12/8 下午 10:59:26 |
| ＜img src=x onerror=a | Re:2001的題目的一些問題: | 2022/12/8 下午 11:01:41 |
主題： | |
暱稱： | 火星人刑事 |
| 留言日期： | 2003/10/22 下午 08:48:47 |
| 留言IP： | |
| 內容： | >請問有人知道2001年國中組題目E 撿石頭 的解法嗎？ 因為那題的情況很多ㄟ, 可能前面有1個大的可以撿, 但是如果捨去不撿, 而使後面能夠撿更多的話, 那情況就多了, 還是說主辦單位的輸入資料不會那麼複雜？ 這是一題很經典的題目, 稱為最長遞增子序列, 為Dynamic Programming演算法的基本作業... 只是比較麻煩的是這次的序列長度可以多達10^5個數字, 單純的Θ(n^2)的演算法應該是沒辦法在時間內跑完, 我剛才嘗試光是跑10^10的空迴圈就跑了數十秒, 即使跑得完也是非常time critical, 我認為應該是要改變DP table的存法來爭取執行時間... 不過最近的動畫有不少好看的所以懶得實作了. :p |