2013-03-05 19:26:41Morris
[ZJ][單調隊列] a605. 交錯和
內容 ：
給定一個整數數列 <an>，考慮下標數列 <bm>，其中 m≠0 且 1≦b1＜b2＜...＜bm≦n，我們定義交錯和 σb = ab1-ab2+ab3-ab4+...。
已知 bi+1-bi≦δ，試求 σb 的最大值。
輸入說明
：
測試資料第一行有兩個整數 n(n≦1000000) 與 δ(1≦δ≦n-1)。
接下來有 n 個整數，其中第 i 個整數為 ai。
輸出說明
：
輸出 σb 的最大值。
範例輸入 ：
5 1 1 4 3 2 5 ----我是分隔線---- 5 2 1 4 3 2 5
範例輸出 ：
6 ----我也是分隔線---- 7
提示
：
出處
：
/* Problem: a605 "交錯和" from 原創問題，如有雷同，純屬巧合 */
/* Language: CPP (994 Bytes) */
/* Result: AC(98ms, 325KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-03-05 19:15:11 */
/************************************************************************/
#include <stdio.h>
#include <deque>
using namespace std;
struct E {
long long v;
int lab;
};
int main() {
int n, m, i;
deque<E> Q, NQ;
scanf("%d %d", &n, &m);
long long ans = -(1LL<<60), x;
E p, q;
for(i = 0; i < n; i++) {
scanf("%lld", &x);
while(Q.front().lab < i-m)
Q.pop_front();
while(NQ.front().lab < i-m)
NQ.pop_front();
p.v = x, p.lab = i, q.lab = i;
if(!NQ.empty() && NQ.front().v > 0)
p.v = NQ.front().v + x;
if(!Q.empty()) {
q.v = Q.front().v - x;
if(q.v > ans)
ans = q.v;
while(!NQ.empty() && NQ.back().v <= q.v)
NQ.pop_back();
NQ.push_back(q);
}
if(p.v > ans)
ans = p.v;
while(!Q.empty() && Q.back().v <= p.v)
Q.pop_back();
Q.push_back(p);
}
printf("%lld\n", ans);
return 0;
}