題目：http://poj.org/problem?id=1207
給一正整數n，如果n=1就結束，n是奇數就3n+1，偶數就減半
原則上n<1000000的時候都會回到1
例如n=22會有過程：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
共16個數字，即長度16
問介於整數p和q之間這種3n+1鍊最長的鍊是多長
程式碼：http://codepad.org/qzZ3UMvT
心機：給定p,q，p不一定小於q。再來，輸出的時候還是得照原本的順序
實際上本質就是模擬、找最大
記錄兩個優化(我的程式只有用第一個)
1.記憶化搜索
唯獨需要注意假如n範圍到10000，
你可能會需要30001這種資料，表格要開大一點
2.線段樹&RMQ
才能快速的給出每筆詢問範圍內的最大值
沒有留言:
張貼留言