2015年1月29日 星期四

2015/01/29 ZJ a605: 交錯和

// http://zerojudge.tw/ShowProblem?problemid=a605
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

#define INF 2e15
typedef long long ll;

ll DP1[2000000], DP2[2000000];
deque<ll> d1, d2;

int A[2000000];

int N, D;

int main()
{
    fill(DP1, DP1+2000000, -INF);
    fill(DP2, DP2+2000000, -INF);

    scanf("%d %d", &N, &D);

    for(int Ni = 1; Ni <= N; Ni++)
        scanf("%d", &A[Ni]);

    DP1[1] = A[1];
    d1.push_back(1);

    DP2[1] = -INF;
    d2.push_back(1);

    ll Ans = A[1];

    for(int Ni = 2; Ni <= N; Ni++)
    {
        while( d1.front()+D < Ni ) d1.pop_front();
        while( d2.front()+D < Ni ) d2.pop_front();

        DP1[Ni] = A[Ni];

        DP1[Ni] = max(DP1[Ni], DP2[d2.front()]+A[Ni]);
        DP2[Ni] = max(DP2[Ni], DP1[d1.front()]-A[Ni]);

        while( !d1.empty() && DP1[d1.back()] <= DP1[Ni] ) d1.pop_back();
        while( !d2.empty() && DP2[d2.back()] <= DP2[Ni] ) d2.pop_back();

        d1.push_back(Ni);
        d2.push_back(Ni);

        Ans = max(Ans, DP1[Ni]);
        Ans = max(Ans, DP2[Ni]);
    }

    printf("%lld\n", max(DP1[N], DP2[N]));
}

沒有留言:

張貼留言