구간 나누기(DP)

 

https://www.acmicpc.net/problem/2228

2228번: 구간 나누기

 

Top-Down 방식의 다이나믹 프로그래밍 기법을 사용한다.

 

DP[N번째 숫자][M개의 구간]으로 정의한다.
DP에 저장되는 값은 N번째 숫자까지 M개의 구간을 만들때 가능한 숫자의 최대합.

 

M개의 구간을 만들어야 하는 상황에서 N번째 숫자에 도달했다면 가능한 경우의 수는 다음과 같다.

 

1. N번째 숫자를 M번째 구간에 포함시키지 않는다.

-> DP[N][M] = DP[N-1][M]

 

2. N번째 숫자를 M번째 구간에 포함시키는 모든 경우의 수를 판단한다.

0~N의 숫자에서 M개의 구간의 구간합 = 0~K의 숫자에서 M-1개의 구간의 구간합 + K~N의 숫자를 1개의 구간으로 만들고 이 구간의 구간합

-> DP[N][M] = DP[K-2][M-1] + Sum(K ~ N), (0 < K <= N)

 

다음과 같은 점화식을 토대로 재귀함수를 호출해주면 된다.

#include <iostream>
using namespace std;

int n, m, num[100], sum[100], dp[100][100];

int solve(int idx, int seq)
{
	if (idx + 1 < 2 * seq - 1)return -987654321;
	if (seq <= 0) return 0;
	if (dp[idx][seq]) return dp[idx][seq];

	int ret = -987654321;
	ret = max(ret, solve(idx - 1, seq));
	for (int i = idx; i >= 0; i--)
	{
		ret = max(ret, solve(i - 2, seq - 1) + sum[idx] - sum[i - 1]);
	}

	return dp[idx][seq] = ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> num[i];
		if (i == 0) sum[i] = num[i];
		else sum[i] = sum[i - 1] + num[i];
	}

	cout << solve(n - 1, m) << '\n';
}