Re: [其他] 遞增的山頂(路徑)

[suhorng ( )]

不確定有沒有偏離這個板的內容 (是 CSAPC'08 的 Skyline 吧)

首先直接找出一個 O(n^2 * n^2) 的 dynamic programming 方法

這樣以原題的配分大概可以拿到 40%

然後一步步把轉移壓到 O(1), 就夠快了











-



設狀態 dp[n][h] 代表位置在 n 時、最右邊的山高為 h 的山稜數 (其中 n 為偶數)

顯然可以想到: 山稜線必然(非嚴格)遞增

所以 dp[n][h] 的數目即為所有位置更左邊、山高不超過 h 的山稜數的和

                                 j  i-2j+2k-2
細分寫出可得遞迴式為 dp[i][j] = Σ (    Σ   dp[l][k] )
                                k=1   l=i-2j

因此狀態數 * 轉移花費可得 DP 式時間複雜度 O(n^4)

透過對 i 的部份預處理加總排容，先把時間複雜度降到 O(n^3)

然後可以觀察到：當 i'=i-2, j'=j-1 的時候，i-2j = (i')-2(j')

所以還可以再均攤：

            j  i-2j+2n-2
dp[i][j] = Σ (    Σ   dp[m][n] )
           n=1   m=i-2j

            i-2             j-1  i-2j+2n-2
         =   Σ  dp[p][j] + Σ (    Σ   dp[m][n] )
           p=i-2j           n=1   m=i-2j

            i-2             j-1  (i-2)-2(j-1)+2n-2
         =   Σ  dp[p][j] + Σ (       Σ        dp[m][n] )
           p=i-2j           n=1   m=(i-2)-2(j-1)

            i-2
         =   Σ  dp[p][j] + dp[i-2][j-1]
           p=i-2j

這樣就可以把轉移的總花費降到 O(1)，總時間複雜度降為 O(n^2)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.115.144.234
推 Cidolfas    :感謝，我的確是這題目解不出來XD
推 Cidolfas    :話說此數列到底是不是Motzkin numbers?前六個我手算
→ Cidolfas    :一樣，但是解答版本的第24(48)個輸出顯示就不同了...
→ Cidolfas    :解答是：302341411。Motzkin第24個數是319727797
→ suhorng     :那就不是了吧XD? 既然有不同的?
→ suhorng     :不然可以自己寫程式枚舉或O(n^4)DP一下,枚舉的話可以
→ suhorng     :跑到n = 40~42, 因為還要除以2 XD
→ suhorng     :n=16 (第八項) 就不一樣囉
推 Cidolfas    :嗯，看來這是新的數列串。再次感謝～