close
四星的題目耶(心)
不過有點像是亂過的，總之莫名其妙就AC了
// 順便慶祝Accepted回家了′▽`)
//可惜紅色不見了(咦)

感謝sa同學索尼板上提供的cut


聽說本來有人說要用DP才會過
不過實際上是DFS也可以通
但需要有點技巧這樣



提供一下我的作法好了


--------------′▽`)′▽`)′▽`)′▽`)′▽`)′▽`)′▽`)--------------------

重點是在於排序
排序過後(由大到小)
就可以比較方便處理

為什麼呢？
因為本來是雜亂無章、等於說你要一個一個拼起來看看長度夠不夠 或是超過
會產生至少O(n^2)的處理時間
再加上遞迴
還有現在的ACM系統3秒的limit
可想而知 一定會TLE

排序後還有幾個特殊的處理點

這題一開始的處理大家應該都有想到吧
就是把平均每邊的長度算出來
然後去處理

可以cut掉的點
第一個就是長度和不能整除4
另一個就是 有超過邊長長度的棍子
//這個很重要，因為如果你沒有咖掉這裡，那麼就會跑進去 把所有情形都跑完Orz
//TLE最主要好像是這個點跟排序那個點

另外的小技巧就是遞迴中的迴圈 每次要從哪個數字開始？
可以思考一下～

還有據說就是你可以做到三個邊就不需要做第四個邊了
因為和是固定的XD

擋重複的部份我自己實做竟然沒有差到什麼秒數
//重複的就是同樣長度的放在同一個地方
代表可能性
(1)測資中數字的重複性不高
(2)測資因為數字不多 就算重複也不會怎樣
(3)其實我沒有擋到重複(炸飛)

我再研究看看好了\(￣▽￣\)﹏﹏
//有興趣研究的話我的程式碼在這裡http://src.wtgstudio.com/?1C6hhJ
//不過他有點醜(汗)


目前秒數停留在0.050

//傳說中的強者DK是0.008耶XD

大概是這樣～
arrow
arrow
    全站熱搜

    aikosenoo 發表在 痞客邦 留言(1) 人氣()

    E-mail轉寄