deque를 이용한 다이나믹프로그래밍

BOJ)5977 Mowing the Lawn 라는 문제를 풀 때 이용한 테크닉이다.

문제: icpc.me/5977

시퀀스가 주어질 때 주어진 시퀀스에서 수를 선택하여 최댓값을 만들어야 하는데 수를 연속으로 k이하로 선택가능할 때 답을 출력하는 문제이다.

예를 들어서 n이 5고 k가2라면 (1,2) (4,5) 이런식으로 연속된 수열은 최대 k까지 선택하여야 한다.

문제만 보면 당연히 다이나믹 프로그래밍을 떠올릴 수 있다.

하지만 점화식을 세우다보면 n이 너무 크기때문에 곤란할 수 있다. 하지만 일단 점화식을 세워보자

dp[i]는 i번째 인덱스까지 수열을 처리하였을 때 최댓값이라고 정의를 한다면

dp[i] =max(psum[i]- psum[j]+ dp[j-1]) j:(i-k+1 ~ i) 

라는 수식이 세워진다. 하지만 j의 범위 때문에 dp테이블을 채우려면 n^2의 시간이 필요하다

하지만 조금의 트릭을 사용하여 시간을 줄일 수 있다.

점화식에서 psum[i]는 j값에 영향받지않는 고유한 값이다. 따라서 우리는 j구간중에서 dp[j-1]-psum[j]의 최댓값만 구하면 된다.

이 수식의 j값을 i보다 작기 때문에 dp[i]를 빌드하면서 dp[i-1]-psum[i]를 매번 priority queue에 넣어준다면 굳이 모든 j를 순회하지 않고 가져올 수 있다. 

단 이때 dp[i-1]-psum[i]와 함께 i를 함께 pair형으로 삽입해주어 만약 pq의 최댓값의 인덱스 i가 현재 구간에서 j를 벗어난다면 pop을 해주면 된다. 이는 뒤에 구할 i+1~n에서도 필요없는 구간이기 때문에 지워져도 된다.

따라서 이러한 방법으로 dp를 nlogn에 구할 수 있다.

여기서 pq대신 deque를 이용하면 이를 O(n)에 구할 수 있다.

deque으로 최댓값을 관리하는 방법은 http://jason9319.tistory.com/346을 참고하면 된다.

pq를 이용한 소스

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
ll n, k, dp[100010], a[100010], p[100010];
int main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        p[i] = p[i - 1] + a[i];
    }
    priority_queue<pair<ll, ll>> pq;
    pq.push({ dp[0],0 });
    for (int i = 1; i <= n; i++) {
        while (pq.top().second < i - k) 
            pq.pop();
        dp[i] = p[i] + pq.top().first;
        pq.push({ dp[i - 1] - p[i],i });
        dp[i] = max(dp[i], dp[i - 1]);
    }
    printf("%lld\n", dp[n]);
    return 0;
}

deque를 이용한 소스

#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long ll;
ll n, k, dp[100010], a[100010], p[100010];
deque<pair<ll, ll>> dq;
int main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        p[i] = p[i - 1] + a[i];
    }
    dq.push_back({ dp[0],0 });
    for (int i = 1; i <= n; i++) {
        while (dq.size() && dq.front().second < i - k)
            dq.pop_front();
        dp[i] = p[i] + dq.front().first;
        while (dq.size() && dq.back().first < dp[i - 1] - p[i])
            dq.pop_back();
        dq.push_back({ dp[i - 1] - p[i] ,i });
        dp[i] = max(dp[i], dp[i - 1]);
    }
    printf("%lld\n", dp[n]);
    return 0;
}