발상
핵심은 추가할 소를 고르는게 아니라 제거할 소를 고르는 것이다. 최소 번째 소마다 한마리를 골라 그 잔디깎이 실력의 합을 최소로 하는 조합의 여집합이 문제에서 요구하는 잔디깎이 실력을 최대로 하는 조합이다. 번 칸 이내로 건너뛸 수 있으므로 현재 위치를 라고 하면 이전 위치를 고를 수 있는 범위는 이다. (각 위치의 최적값 중 최소값)+(현재 위치 소의 잔디깎이 실력)이 현재 위치의 최적값이 된다. 문제는 정렬되지 않은 범위 중 최소값을 구하는 알고리즘은 이므로 개의 구간을 모두 이렇게 구할 경우 시간복잡도가 가 된다.
따라서 모든 구간에 대해 별도로 최솟값을 구하는게 아니라 이전 구간의 정보를 Deque에 저장하고 그 정보를 활용해 상수 시간에 구간의 최적값을 업데이트하는 자료구조를 만들 수 있다. 구간이 옮겨질 때마다 실제로 덱에 발생하는 변경점은 인덱스가 벗어난 원소 1개 제거, 새로 추가되는 원소 1개 추가가 전부이다. 구간의 값들 중 딱 1개만 새로운 수로 갱신되는 것이다. 주어진 수열을 인덱스 순으로 순회할 때 앞서 나왔던 수 가 현재 수 보다 크다면 그 수는 이상의 인덱스에서는 절대 최솟값이 될 수 없다. ( 라는 점을 꼭 기억해야 한다. ) 그 이유는 아래와 같다.
가 어떤 구간 의 최솟값이 되기 위해선 와 같은 구간에 속하면 안된다. 그런데 우리는 탐색할 때 구간을 순차적으로 옮기고 있으므로 구간에서 먼저 벗어나는 수는 가 될 수 밖에 없다. 즉, 와 가 같은 구간에 속하게 되는 시점부터 는 최솟값이 되는 것이 불가능하다. 즉, 는 가 덱에 삽입되는 순간부터 최솟값 후보에서 제외할 수 있다.
마지막으로 답을 구할 때 DP 배열의 사이 구간 중 최솟값을 골라야 한다. 마지막으로 제거한 소부터 마지막 소까지의 거리가 마리 이하가 되는 경우는 모두 정답 후보에 포함되기 때문이다.
점화식
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;
struct node {
ll i, v;
};
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k; vector<ll> arr(n + 1), dp(n + 1); deque<node> dq;
ll s = 0;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
s += arr[i];
}
ll mn = s;
dq.push_front({ 0, 0 });
for (int i = 1; i <= n; i++) {
while (!dq.empty() && i - dq.front().i - 1 > k) dq.pop_front();
dp[i] = (dq.empty() ? 0 : dq.front().v) + arr[i];
while (!dq.empty() && dq.back().v >= dp[i]) dq.pop_back();
dq.push_back({ i, dp[i] });
if (i + k >= n) {
mn = mn < dp[i] ? mn : dp[i];
}
}
cout << s - mn;
return 0;
}