問題概要

正の整数 $K$ と、 $N$ 個の正の整数 $A_{1}, \dots, A_{N}$ が一列に並んでいる。これを左から順に何個かのグループに分けていく。ただし、各グループに含まれる要素の個数は $M$ 個以下でなければならない。

各グループのコストは次のように定義される。

$K + ( (グループ内の整数の最大値) - (グループ内の整数の最小値) ) \times (グループの要素数)$

またグループ分け全体のコストは、各グループのコストの総和で定める。グループ分け全体のコストの最小値を求めよ。

制約

$1 \le N \le 20000$
$1 \le M \le 1000$

考えたこと

まずはグループのコストの意味を簡単に掴んでみる。

グループには 1 個あたり固定コスト $K$ がかかるのでグループの個数はなるべく小さくしたい
各グループのサイズが大きすぎると、(最大値) - (最小値) の値が大きくなりがちなので、それが適度に小さくなるようにしたい

ということで、各グループのサイズの取り方については、トレードオフな関係にあることがわかる。こういう状況では Greedy は考えづらくて、DP っぽい感がある。

区間分割していく DP

ちょうど今回の問題にピッタリ当てはまる DP がある。一列に並んだ $N$ 個のアイテムをいくつかの区間に分割していくタイプの DP はめっちゃよくみる。けんちょん本でも、5.6 節で解説している。

こんな感じの DP を組む。

${\rm dp} \lbrack n \rbrack$ := 先頭から $n$ 個のアイテムを、いくつかの区間に分割していったときの、各区間のコストの総和の最小値

そしてこんな感じの遷移が作れる。

chmin(dp[j], dp[i] + cost(i, j));

ここで、cost(i, j) は、区間 [i, j) のコストを表している。cost(i, j) については、あらかじめ前処理しておくのがいい。このような区間 DP で計算量は $O(N^{2})$ となる。

このままでは TLE してしまう (してしまった) が、よく考えると区間 [i, j) の幅は $M$ 以下でよいので、区間幅を $M$ 以下に限定することで計算量は $O(NM)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, M, K;
    cin >> N >> M >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    const long long INF = 1LL<<60;

    vector<vector<long long>> cost(N+1, vector<long long>(M+1, 0));
    for (int i = 0; i < N; ++i) {
        long long vmin = INF, vmax = 0;
        for (int j = i; j < N && j+1-i <= M; ++j) {
            vmin = min(vmin, A[j]);
            vmax = max(vmax, A[j]);
            cost[i][j+1-i] = K + (vmax - vmin) * (j+1-i);
        }
    }


    vector<long long> dp(N+1, INF);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j <= N && j-i <= M; ++j) {
            dp[j] = min(dp[j], dp[i] + cost[i][j-i]);
        }
    }
    cout << dp[N] << endl;
}