오늘은 시간이 없어서 뭔가 기록할 만큼 공부한건 없고, 타임라인에 문제가 보이길래 오랜만에 또 ps 문제를 풀어봤다.

문제를 읽고 떠오르는 몇 가지 중요한 관찰을 적어보자.

  • 주어진 바구니의 위치를 정렬했을 때, 방문한 지점은 $[l, r]$ 처럼 연속된 형태여야 한다. (이동중에 지나게 되는 사탕을 먹지 않으면 손해니까)
  • 모든 바구니의 사탕 수가 동일하므로, 문제를 바꿔 생각할 수 있다: $t_i$를 $i$번째 사탕 바구니에 방문했을 때의 시간이라고 하면, $~\mathrm{maximize}~ m \cdot n - (t_1 + t_2 + … + t_n)$ $\Leftrightarrow ~\mathrm{minimize}~ \sum_{i=1}^n t_i$ 을 풀면 된다.

이걸로 충분하면 좋겠으나, 아직 해결해야 할 의문이 남아있다.

  1. 과연 모든 사탕을 먹는게 최적일까? 당연히 아니다. 어떤 $k < n$인 $k$에 대해, $t_k \geq m$이 되면 더 이상의 바구니를 방문할 이유가 없으니까.
  2. $k$개의 바구니만 방문하는 경우에 방문하게 되는 바구니의 구간은 $k-1$개의 바구니만 방문하는 경우의 구간을 포함할까? 이게 되면 바이너리 서치를 통해 최적의 $k$를 찾을 수 있을 텐데, 아쉽게도 성립하지 않는 케이스를 찾을 수 있다: 바구니가 [-99, -98, -97, -1, 0, 1, 50, 100] 과 같이 놓여있는 경우, 4개의 바구니를 방문하는 경우와 5개의 바구니를 방문하는 경우에 방문하게 되는 바구니의 구간이 전혀 다름을 확인할 수 있다.

지금까지 생각해본 내용을 바탕으로 해법을 구상하면 이렇게 정리할 수 있다.

  • 상태를 $(\mathrm{left}~, ~\mathrm{right}~, ~\mathrm{is\_right}~, ~\mathrm{remaining})$ 으로 정의하고, 다이나믹 프로그래밍으로 최소 시간을 구하자! $~\mathrm{left}~, ~\mathrm{right}~$: 이미 방문한 구간의 끝 점, $~\mathrm{is\_right}~$: 현재 위치가 오른쪽 끝 점인지의 여부, $~\mathrm{remaining}~$: 앞으로 몇 개의 바구니를 더 선택할 예정인지.
    • $O(n^3)$의 시간과 공간으로 문제를 해결할 수 있다.
    • 각 $~\mathrm{remaining}~$에 대해 배열을 재활용하면 공간복잡도는 $O(n^2)$으로 줄일 수 있다.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
using ll = long long;

int n, m;
int c[311];
ll d[2][311][311];

ll candy(int l, int r, int right, int k)
{
    if (k == 0) return 0;
    ll & ret = d[right][l][r];
    if (ret != -1) return ret;
    ret = m *1LL* k;

    int pos = right ? c[r] : c[l];
    if (l > 0) {
        int dist = abs(pos - c[l - 1]);
        ret = min(ret, candy(l - 1, r, 0, k - 1) + dist *1LL* k);
    }

    if (r + 1 < n) {
        int dist = abs(pos - c[r + 1]);
        ret = min(ret, candy(l, r + 1, 1, k - 1) + dist *1LL* k);
    }

    return ret;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", c + i);

    int has_zero = 1;
    if (find(c, c + n, 0) - c >= n) c[n++] = has_zero = 0;

    sort(c, c + n);
    int start = lower_bound(c, c + n, 0) - c;

    ll ans = 0;
    for (int k = n; k > 0; k--) {
        memset(d, -1, sizeof d);
        ans = max(ans, m *1LL* k - candy(start, start, 0, k - 1));
    }

    printf("%lld", ans - m * !has_zero);
    return 0;
}