224 words
1 minutes
[BOJ] 연세워터파크
| TimeLimit | MemoryLimit | Condition | TAG | 
|---|---|---|---|
| 1s | 128MB | (2 ≤ N ≤ 100000 1 ≤ D ≤ N-1)  | Dynamic Programming | 
그냥 전형적인 DP인데 약간 새로운 관리법이 추가된 dp? 느낌이네요. 생각보다 재밌는 문제였습니다.
한번씩 풀어보면 좋을 듯 합니다.
정답 코드
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
using ll = long long;
int n, d;
ll dp[100'001];
ll nums[100'001];
map<ll, ll> current;
set<ll> keys;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> d;
    ll result = -1e10;
    for(int i = 0; i < n; i++) cin >> nums[i];
    
    for(int i = 0; i < d; i++){
        ll previous = keys.empty() ? 0 : *--keys.end();
        dp[i] = max(previous + nums[i], nums[i]);
        
        keys.insert(dp[i]);
        current[dp[i]]++;
        
        result = max(dp[i], result);
    }
    for(int i = d; i < n; i++){
        ll previous = *--keys.end(); // 일단 전에 있던 것들 중에서 올 수 있는 가장 쩌는 애를 데려오겟다ㅓ
        dp[i] = max(previous + nums[i], nums[i]);
        
        keys.insert(dp[i]);
        current[dp[i]]++;
        
        
        current[dp[i - d]] --;
        if(!current[dp[i - d]]) keys.erase(dp[i-d]);
        
        result = max(dp[i], result);
    }
    
    
    cout << result;
    
    
    return 0;
}[BOJ] 연세워터파크
https://compy07.github.io/Blog/posts/boj/15678/
