a605: 交錯和
Tags : DP
Accepted rate : 56人/64人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-03-14 13:43

Content
給定一個整數數列 <an>,考慮下標數列 <bm>,其中 m≠0 且 1≦b1<b2<...<bm≦n,我們定義交錯和 σb = ab1-ab2+ab3-ab4+...。
已知 bi+1-bi≦δ,試求 σb 的最大值。
Input
測試資料第一行有兩個整數 n(n≦1000000) 與 δ(1≦δ≦n-1)。
接下來有 n 個整數,其中第 i 個整數為 ai(|ai|≦1000000000)。
Output
輸出 σb 的最大值。
Sample Input #1
5 1
1 4 3 2 5
----我是分隔線----
5 2
1 4 3 2 5
Sample Output #1
6
----我也是分隔線----
7
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <10M
不公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
DP
出處:
原創問題,如有雷同,純屬巧合 [管理者:
xavier13540 (柊 四千)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」