BOJ)11985 오렌지 출하

문제: icpc.me/11985

오렌지를 연속적으로 M개 이하 씩 포장할 때 포장비용이 주어질 때 전체를 포장했을 때 포장비용의 최솟값을 출력하는 문제이다.

이 문제는 다이나믹 프로그래밍으로 해결할 수 있다,

DP[i]= i까지 포장하는데 필요한 최소 비용

이라고 생각하면 

for( j= i-m+1~i)에 대해서 

MIN(dp[j-1]+k+(i-j+1)*(max(i~j)-min(i~j))가 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, m, k, dp[20020], a[20020];
int main() {
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (ll i = 1; i <= n; i++) {
        dp[i] = 1e15;
        ll x = a[i], y = a[i];
        for (ll j = i; j >= max(1LL, i - m + 1); j--) {
            x = max(x, a[j]);
            y = min(y, a[j]);
            dp[i] = min(dp[i], dp[j - 1] + k + (i - j + 1)*(x - y));
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}