잔디밭 가꾸기 (JUNGOL 3621)

https://jungol.co.kr/problem/3621

---

아이디어

모노톤 덱을 이용해줍시다.

dp[i]를 i번째까지의 소들을 가지고 얻을 수 있는 최댓값으로 정의합시다. 이 경우는 두가지로 나눌 수 있습니다. 

- i번째 소를 선택하지 않는 경우 -> dp[i-1]의 값과 동일

- i번째 소를 선택하는 경우 -> i-K이상의 j를 선택하여 (dp[j-1]-sum[j])+sum[i]중 최댓값을 저장함

 

두번째 경우는 j에 의존하는 부분과 i에 의존하는 부분으로 나눌 수 있기 때문에 모노톤 덱을 이용해서 (dp[j-1]-sum[j])의 최댓값을 저장해주면 됩니다. 이 덱은 앞에서 뒤로 갈수록 j값은 증가, dp[j-1]-sum[j]값은 감소하며, 새로운 값을 넣을때에는 뒤에 넣는데, 뒤에 dp[j-1]-sum[j]값이 더 작은것이 존재한다면 빼고 넣어줍니다.

---

소스코드

#include <iostream>
#include <deque>
#define ll long long
using namespace std;

ll dp[101010]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,K,i,x,sum=0;
    deque <pair <ll,ll> > dq;
    dq.push_back({0,0});

    cin>>N>>K;
    for (i=1;i<=N;i++)
    {
        cin>>x;
        sum+=x;
        if (dq.front().first<i-K) dq.pop_front();
        dp[i]=max(dp[i-1],sum+dq.front().second);

        while (dq.back().second<=dp[i-1]-sum) dq.pop_back();
        dq.push_back({i,dp[i-1]-sum}); 
    }

    cout<<dp[N];
}