a146. 小蓁的樓梯人生思考題(困難版)

內容

小蓁是一個喜歡思考的學生，典型的理科女，她的教室在四樓，在每天上下樓梯時，她思考出一個爬樓梯的邏輯遊戲問題，每天爬樓梯時腦海裡就在執行這個遊戲：

每一步可以往上走 1 階或 2 階，開始位置在第 0 階，從第一階開始每階都有一個數字，踩在第 i 階，分數就要扣第 i 階的數字，請問當爬到第 n 階的最少的扣分是多少。

小蓁的同學也就是你本人覺得這個遊戲實在太簡單了，因此你輕鬆地使用了 DP 的程式技巧就幫她解決了這個問題，但是你在解決這個問題的過程根本無法體會到 DP 的精華，因此你幫這個遊戲做了以下變更，讓遊戲的內容更加有趣。

• 每一步不再只是可以往上走 1 階或 2 階，然而每一個階梯都會限制到達此階時，上一步至多可以走的階數。

• 每一個階梯現在可能為扣分或加分，加分會以正數表示，扣分會以負數表示，可能有 0。

現在請你求出正負相抵後，爬到第 n 階的最多的加分是多少，如果是扣分請以負數表示。

輸入說明

第一行是正整數 n，代表階梯的總數。

第二行有 n 個正整數 a_i，依序代表第 1 階開始的分數，數字間以空白隔開。

第三行有 n 個正整數 k_i，k_i代表跳至第 i 階的前一步至多可以有幾階，亦即你只能從第 i - k_i階以上的階層到達第 i 階。

• 1 ≤ k_i≤ i

• -10⁹ ≤ a_i≤ 10⁹

輸出說明

輸出走到第 n 階的最大得分。

範例輸入 #1

#test input 1:
6
2 -1 3 -5 2 1
1 2 2 3 2 4
 
#test input 2:
6
-3 -3 -3 -3 -3 -3
1 2 1 2 2 1

範例輸出 #1

#test output 1:
8

#test output 2:
-12

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <10M
公開測資點#3 (5%): 1.0s , <10M
公開測資點#4 (5%): 1.0s , <10M
公開測資點#5 (5%): 1.0s , <10M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

dp, data structures (CF 1600)

10% 的測資滿足 1 ≤ n≤ 5000。

40% 的測資滿足 1 ≤ n≤ 300000， k_i+1≤ k_i+1，1 ≤ i≤ n-1。

50% 的測資滿足 1 ≤ n≤ 300000。

標籤:

出處:

[管理者：

iris@stu.cch... (iris)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」