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/