Educational codeforces #69 div2 D - Yet Another Subarray Problem (dp)

https://codeforces.com/contest/1197/problem/D

까다로운 dp문제

 

<문제설명>

최대 3e5개의 숫자 배열이 주어진다. 연속된 부분수열 a[l..r]의 비용이 다음과 같을 때, 그 최대값을 구해라.

(빈 부분수열의 비용은 0이다. 따라서 답의 최댓값은 0이다.)

 

<풀이>

i번째에서 끝나는 연속된 부분수열은 다음 네 가지 경우로 나눌 수 있다.

첫번째 경우: 0

두번째 경우: a[i]-k

세번째 경우: 

네번째 경우: psum(0,i)-k

 

이걸로 for문 디피하면된다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
typedef long long ll;
const ll MAX = 300005;

int main() {
	FAST;
	ll n, m, k, a[MAX], dp[MAX], psum[MAX] = { 0 };
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		psum[i] = (i == 0 ? a[i] : psum[i - 1] + a[i]);
	}

	ll ans = 0;
	for (int i = 0; i < n; i++) {
		dp[i] = max(a[i] - k, (ll)0); //1,2번 상황
		ll temp = -1e9;
		for (int j = i - 1; j >= max(i - m, (ll)0); j--)
			temp = max(temp, dp[j] - k + psum[i] - psum[j]);  //3번
		if (i < m) temp = max(temp, psum[i] - k);  //4번

		dp[i] = max(dp[i], temp);
		ans = max(ans, dp[i]);
	}

	cout << ans << '\n';

}

 

 

<풀이>

상황이 양자화?된 문제에 대해 dp를 적용할 수 있다는 것을 알려주는 문제인 듯 하다.

(구간 길이가 0 / 1~m / 2~2m / 3~3m ... 에 따라서 구간합에 k, 2k, 3k를 빼준다)