けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2016 A - オレンジの出荷 (AOJ 0625, 難易度 6)

区間を分割していくタイプの DP。とても教育的な典型問題という感じですね。

類題は超多数!!!

drken1215.hatenablog.com

問題概要

正の整数  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;
}