Codeforces 1077F1, 1077F2 Pictures with Kittens (easy, hard version)

Pictures with Kittens (easy version)
(http://codeforces.com/problemset/problem/1077/F1)
Pictures with Kittens (hard version)
(http://codeforces.com/problemset/problem/1077/F2)

난이도가 easy가 2100, hard가 2300인데 사실 그 정도는 아닌 것 같다.
Div3 마지막 문제들이었는데 내 힘으로 풀어서 조금 뿌듯하다. 근데 대회에서 푼 건 아니라서 조금 아깝다.
이런 dp 최적화는 간단하고 충분히 또 나올만 해서 풀이를 적어둬야겠다.

easy는 간단하게 dp로 풀 수 있다.
일단 \(D_{i,j}\)를 \(i\)번째 사진을 선택하고 총 \(j\)개를 골랐을 때의 최댓값이라고 한다.
그러면 \(D_{0,0}=0\)으로 두고 \(D_{i,j}=\text{max}(D_{t,j-1})+a_i (i-k\le t\le i-1)\)이다. (물론 도달하지 못 하는 경우는 따로 처리한다.)

그러면 모든 \((i,j)\)쌍에서 \(i-k\cdots i-1\)을 전부 확인해 최댓값을 찾는다면 \(O(nkx)\)의 시간복잡도를 가진다.
easy에서 \(nkx\)는 최대 \(200^3\)이므로 통과할 수 있다.

hard는 \(n,k,x\)가 모두 \(5000\)으로 늘었는데, 하나에 \(\log\)가 붙는 것도 힘들어보이니 셋 중 적어도 하나는 없애야 한다는 의미다.
우선 \(n\)은 지우기 힘들어 보인다. 그리고 위 dp식을 유지하려면 \(x\)도 필수적이다. (물론 이럴 때 dp식을 바꿔야 하는 경우도 있고, 식 자체를 버려야 하는 경우도 있긴 하다.)
그러면 이제 \(k\)를 없앨 방법을 찾아야한다.

위에서는 \((i,j)\)쌍에서 \(i-k\cdots i-1\)를 전부 탐색하며 최댓값을 찾았다.
하지만 관찰해보면, \(i-k\cdots i-1\)은 \(i\)에 따라서 같이 움직인다. 그러니 매번 \(k\)개를 확인하는건 비효율적이다.
\(i\)가 늘어나면 앞에서 한 개 빠지고 뒤에서 한 개 들어오니, 덱을 쓰기 좋아보인다.
앞에서 보며 \(i-k\)보다 앞에 있던 것들은 빼고, 뒤에서 보며 \(D_{i,j}\)를 넣는데 내림차순이 되도록 최댓값을 저장해두면 된다.
이 과정을 거쳤을 때 덱의 앞이 \(\text{max}(D_{t,j-1})(i-k\le t\le i-1)\)가 된다.
이러한 덱을 \(x\)개 관리해주면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
long long a[5001], d[5001][5001];
deque<pair<int, long long> > mx[5001];
bool chk[5001][5001];
 
int main() {
    int n, k, x;
    scanf("%d %d %d", &n, &k, &x);
    for (int i = 1;i <= n;++i)
        scanf("%lld", &a[i]);
 
    chk[0][0] = true;
    mx[0].push_front({ 0, 0 });
    for (int i = 1;i <= n;++i)
        for (int j = min(i, x);j >= 1;--j) {
            if (!mx[j - 1].empty()) {
                while (!mx[j - 1].empty() && mx[j - 1].front().first < i - k)
                    mx[j - 1].pop_front();
                if (!mx[j - 1].empty()) {
                    chk[i][j] = true;
                    d[i][j] = mx[j - 1].front().second + a[i];
                    while (!mx[j].empty() && mx[j].back().second < d[i][j])
                        mx[j].pop_back();
                    mx[j].push_back({ i, d[i][j] });
                }
            }
        }
 
    bool ans = false;
    long long anss = 0;
    for (int i = n - k + 1;i <= n;++i)
        if (chk[i][x]) {
            ans = true;
            anss = max(anss, d[i][x]);
        }
 
    printf("%lld", ans ? anss : -1);
 
    return 0;
}

아마도 연세워터파크 문제에도 이 방식을 적용할 수 있다.