作者DarkPrincex (DP)
看板C_and_CPP
標題Re: [問題] ACM Trainsorting
時間Wed Aug 24 12:42:45 2011
※ 引述《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
→ firejox:DP的不就是可以求出每一個嗎? 08/24 13:20
→ DarkPrincex:用DP的可以找出每個人當終點，可是沒辦法做每個人起點 08/24 13:47
→ firejox:可以處理起點的呀 就倒過來做呀 08/24 15:17
→ firejox:倒過來就變成起點了呀 08/24 15:23
→ DarkPrincex:痾...你直接把我最後留給他想的為什麼要倒著做講出來 08/24 19:21
→ k577887:以1起點 最大LIS+LDS-1不是4+2-1=5嗎 為什最大才4... 08/24 20:03
→ firejox:LDS是2? 再想想吧 你怎麼算的 08/24 20:35
→ dqIpb:以1起點指以1為LDS的第一個數的LDS長度是多少,你有沒有弄懂 08/24 20:37
→ dqIpb:為什麼是LIS+LDS-1? 08/24 20:37
→ k577887:SOR 我一直把它當作整個最長在看...所以1起點LDS 1? 08/24 22:43
→ k577887:-1是扣掉以1起點? 08/24 22:44
→ firejox:-1是扣掉重複的部份 08/24 22:45
→ k577887:謝謝大家 我再想一下!! 08/25 11:26