BOJ 5977번 Mowing the Lawn

문제 링크

N <= 10^5, K <= N

이 문제는 N 이 주어지고 N개의 정수가 주어진다.

N개의 정수 중에 일부만 골라서 합을 최대로 만들어야 하는데

K개를 초과하여 연속된 수를 고를 수가 없다는 제약이 있을 때 최대 합을 구하는 문제이다.

우선 dp 로 부분문제를 정의하고 점화식을 세워보자.

psum[i] : 1~i 번째 수의 합

dp[i] : i 까지 봐줬을 때 최대 합

dp[i] = max(psum[i] - psum[j] + dp[j - 1]) ( i - K <= j <= i )

점화식을 좀 설명하자면 마지막으로 연속된 [j + 1, i] 구간을 선택했고 j번째 수는 선택하지 않았으며

j - 1 번째 수까지는 재귀적으로 최대값을 취하는 것이다.

마지막에 아예 선택하지않는 것도 포함되어있다는 것에 유의.

그럼 일반적인 방법으로는 O(N^2) 이 걸릴 것이다. 그런데 여기선 N 이 커서 안된다.

우선 위의 점화식을 살짝 바꿔보자.

잘 보면 j만 변하는 것이기 때문에 psum[i] 는 공통된 값이라는 것을 알 수가 있고 이것을 밖으로 빼보면 결국

dp[i] = psum[i] + max(dp[j - 1] - psum[j]) (i - K <= j <= i) 라는 것을 알 수가 있다.

그럼 결국 마지막에 연속된 K개의 어떤 값중에 최대만 유지해주면 된다는 것이 핵심이다.

multiset 과같은 자료구조를 사용해도 되지만 이러면 로그가 붙고 

여기서 덱을 사용하면 O(N) 으로 줄일 수가 있다.  그런데 비슷한 문제를 어디서 본 것같다.

여기를 보고오자. 결국 C[j] = dp[j - 1] - psum[j] 라고 정의해보면 저 문제와 정확히 같다는 것을

알 수가 있다. 그럼 끝!

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll psum[100003];
ll A[100003];
ll dp[100003];
deque<int> dq;
int N, K;
ll C(int i){
    return dp[i - 1] - psum[i];
}
int main() {
    fastio();
    cin >> N >> K;
    for(int i = 1 ; i <= N; i++) cin >> A[i];
    for(int i = 1 ; i <= N; i++) psum[i] = psum[i - 1] + A[i];
    for(int i = 1; i <= N; i++){
        while(!dq.empty() && dq.front() < i - K) dq.pop_front();
        while(!dq.empty() && C(dq.back()) <= C(i)) dq.pop_back();
        dq.push_back(i);
        dp[i] = psum[i] + C(dq.front());
        if(i <= K) dp[i] = max(dp[i], psum[i]);
    }
    cout << dp[N];
    return 0;
}