[11985] 오렌지 출하

### DP ###

[11985] 오렌지 출하 : http://boj.kr/11985

<소스코드>

d[i] : i번째 오랜지부터 포장했을 때, 비용의 최소값.

#include <stdio.h>
 
int a[20001];
long long d[21001];
int n, m, k;
 
long long min(long long a, long long b)
{
    return a < b ? a : b;
}
 
long long orange(int s, int e)
{
    long long *ret = &d[s];
    int size, big=0, small=0x7fffffff;
    long long box;
 
    if(s >= e) return 0;
    if(*ret != -1) return *ret;
 
    *ret = 0x7fffffffffffffff;
    size = m < e-s+1 ? m : e-s+1;
    for(int i=0; i<size; i++) {
        if(big < a[s+i]) big = a[s+i];
        if(small > a[s+i]) small = a[s+i];
        box = 1LL*(i+1)*(big-small) + k;
        *ret = min(*ret, box+orange(s+i+1, e));
    }
    return *ret;
}
 
int main()
{
    scanf("%d%d%d", &n, &m, &k);
 
    for(int i=0; i<n; i++) {
        scanf("%d", a+i);
        d[i] = -1;
    }
 
    printf("%lld\n", orange(0, n));
    return 0;
}
 

>> 시간복잡도 : O(NM)