티스토리 뷰

알고리즘 관련/BOJ

BOJ)11985 오렌지 출하

JASON 자손9319 2017. 7. 24. 03:07

문제: 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))가 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14657 준오는 최종인재야!!  (0) 2017.07.29
BOJ)2300 기지국  (0) 2017.07.25
BOJ)11985 오렌지 출하  (0) 2017.07.24
BOJ)10637 Minimum Spanning Tree  (0) 2017.07.21
BOJ)2261 가장 가까운 두 점  (1) 2017.07.09
BOJ)5038 Flight Planning  (0) 2017.07.09
댓글
댓글쓰기 폼