백준 2228번 구간 나누기 C/C++ 풀이

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

2228번: 구간 나누기

이 역시 DP로 푸는 문제.

 

점화식을

 

dp[n][m](n개를 m개의 구간으로 나눴을 때의 최댓값) = dp[n-1][m](n을 포함하지 않고 m개를 선택했을 때의 최대값) 이거나 sum(i부터 n까지의 합) + dp[i - 2](하나의 공백이 있어야하기 때문에 i-2부터)[m-1](구간 하나 줄어들었으니 m-1로)'

 

으로 나타낼 수 있다.

 

 

#include <stdio.h>
#include <algorithm>

using namespace std;

FILE* in = fopen("input.txt", "r");

#define MIN -3276801

int n, m;
int arr[102];
int cache[102][52];
bool visited[102][52];
int sum_c[102][102];
bool vis_sum[102][102];

int sum(int k, int n) {
	if (vis_sum[k][n])
		return sum_c[k][n];
	int sum = 0;
	for (int i = k; i < n; i++)
		sum += arr[i];
	vis_sum[k][n] = true;
	return sum_c[k][n] = sum;
}

int dp(int n, int m) {
	if (m == 0) return 0;
	if (n <= 0)
		return MIN;
	if (visited[n][m])
		return cache[n][m];
	cache[n][m] = dp(n-1, m);
	for (int i = n - 1; i >= 0; i--)
	{
		int tmp = sum(i, n) + dp(i - 1, m - 1);
		cache[n][m] = max(tmp, cache[n][m]);
	}
	visited[n][m] = true;

	return cache[n][m];
}

int main() {
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		fscanf(in, "%d", &arr[i]);
	printf("%d", dp(n, m));

	return 0;
}