이것 저것 &

문제링크: www.acmicpc.net/problem/2616

down-up방식 점화식을 구하지 못해 up-down 방식을 사용했습니다.

한점 기준으로 해당 위치부터 소형 기관차를 사용하는 경우 혹은 사용하지 않는 경우 두가지를 비교해주며 결과값을 도출했습니다.

dp[i][j]는 i번째 위치에서부터  j개의 소형기관차를 사용할때 얻을 수 있는 최대값을 가르킵니다. 이때 점화식은

• max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1])); 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n = 0, k = 0;
int dp[50001][3] = { 0, };
int arr[50001] = { 0, };

int solved(int current, int cnt) {

	if (current > n || cnt == 3)
		return 0;

	int &ret = dp[current][cnt];
	if (ret != -1)
		return ret;

	if ((current + k - 1) <= n)
		ret = max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1]));


	return ret;
}



int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int temp = 0;
		cin >> temp;
		arr[i] = arr[i - 1] + temp;
	}
	cin >> k;
	memset(dp, -1, sizeof(dp));
	cout << solved(1, 0) << endl;

	/*
	for (int i = 1; i <= n; i++)
		cout << arr[i] << endl;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}*/
	return 0;
}

down-up방식도 가능할거 같아 찾아봤습니다.

lyzqm.blogspot.com/2017/03/2616.html

DP[N][M]=max(DP[N][M−1],DP[N−1][M−K]+S[M]−S[M−K] 해당 점화식 사용하셔서 푸는 답도 있습니다.