1866번: 택배

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


$O(n^2)$


각 지점을 시작 지점까지의 거리를 기준으로 오름차순 정렬한다.(=ai)
dp[i]: 1~i번째 지점에 물품을 배송하는데 필요한 최소 비용
dp[i]는 1<=j<i인 모든 j에 대해

(1) 1~j-1 지역에 배송하는데 드는 최소 비용 즉, dp[j-1]
+
(2) j~i 어느 한 지역에 헬리콥터를 이용하여 j-i+1개의 물품을 배송받은 뒤 j~i 지역 각각 하나씩 물품을 배송하는 비용
의 최솟값을 취하면 된다.

(2) 비용을 최소화하기 위해 j~i 지역의 중앙에 위치한 지역에서 헬리콥터로 물품을 배송받아야 한다.
이는 |aj-x| + ... + |ai-x| 의 최솟값이 x=a(i+j)/2일 때이기 때문이다.

이제 j=i -> 1 까지 옮겨가며 aj...ai 의 중앙값을 하나의 변수를 통해 유지해준다면 쉽게 dp를 할 수 있을 것이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[3001], x, y, dp[3001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    scanf("%d%d", &x, &y);
    for (int i = 1; i <= n; i++) {
        dp[i] = a[i] * x + dp[i - 1];
        for (int j = i, t = y; j; j--) {
            t += (a[i + j + 1 >> 1] - a[j])*x;
            dp[i] = min(dp[i], dp[j - 1] + t);
        }
    }
    printf("%d", dp[n]);
    return 0;
}