Re: [問題] ACM Trainsorting

看板C_and_CPP作者 (DP)時間12年前 (2011/08/24 12:42), 編輯推噓0(0推 0噓 13→)
留言13則, 4人參與, 最新討論串3/4 (看更多)
※ 引述《k577887 (HaHa-Dog)》之銘言： : 問題(Question)： : 這一題為什要從後面看過來算LIS 跟LDS : 為什從第一個算會錯誤... : http://ppt.cc/s3cm : 討論地方 1 2 4 3 7 6 : 從第一個算起 7 6 3 2 1 怎來的.... 有一種想法是這樣的， 先假設1一定要用， 所以接下來一定是從1開始， 往左越來越大往右越來越小。 (也就是把1之前的東西砍光接著做LIS+LDS-1) 接下來我們嘗試拿2開始， 做剛才的事情。 之後從4開始嘗試... 一直試到從6當頭為止， 我們把每個東西拿來當開頭都嘗試過了， 看最長的那串多長就對了。 為什麼會對呢？ 我們假設規定某個東西一定要拿， 那它之後的東西都只能丟左邊或右邊， 所以可以強迫算出來的LIS和LDS只有中間的開頭重複， 因此，只要拿每個數字當開頭，計算LIS+LDS-1， 最大的那組就是答案了。 不過，這樣需要跑O(N^3) (假設LIS用N^2的方法) 至於為什麼從後面往前跑可以加速到O(N^)呢？ 就留著讓你自己想想看了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.49.243
→
08/24 13:20, , 1F
DP的不就是可以求出每一個嗎?
08/24 13:20, 1F
→
08/24 13:47, , 2F
用DP的可以找出每個人當終點，可是沒辦法做每個人起點
08/24 13:47, 2F
→
08/24 15:17, , 3F
可以處理起點的呀 就倒過來做呀
08/24 15:17, 3F
→
08/24 15:23, , 4F
倒過來就變成起點了呀
08/24 15:23, 4F
→
08/24 19:21, , 5F
痾...你直接把我最後留給他想的為什麼要倒著做講出來
08/24 19:21, 5F
→
08/24 20:03, , 6F
以1起點 最大LIS+LDS-1不是4+2-1=5嗎 為什最大才4...
08/24 20:03, 6F
→
08/24 20:35, , 7F
LDS是2? 再想想吧 你怎麼算的
08/24 20:35, 7F
→
08/24 20:37, , 8F
以1起點指以1為LDS的第一個數的LDS長度是多少,你有沒有弄懂
08/24 20:37, 8F
→
08/24 20:37, , 9F
為什麼是LIS+LDS-1?
08/24 20:37, 9F
→
08/24 22:43, , 10F
SOR 我一直把它當作整個最長在看...所以1起點LDS 1?
08/24 22:43, 10F
→
08/24 22:44, , 11F
-1是扣掉以1起點?
08/24 22:44, 11F
→
08/24 22:45, , 12F
-1是扣掉重複的部份
08/24 22:45, 12F
→
08/25 11:26, , 13F
謝謝大家 我再想一下!!
08/25 11:26, 13F
‣ 更多 DarkPrincex 的文章
文章代碼(AID): #1EL857Y- (C_and_CPP)
‣ 更多 DarkPrincex 的文章
文章代碼(AID): #1EL857Y- (C_and_CPP)