問題概要

$N$ 個の区間があって、長さが $D_{1}, D_{2}, \dots, D_{N}$ である。これらすべてを 2 種類の区間で被覆したい。

長さが $L_{1}$ である区間が $K_{1}$ 個 (1 個あたりコストは $C_{1}$ )
長さが $L_{2}$ である区間が $K_{2}$ 個 (1 個あたりコストは $C_{2}$ )

を用いて、 $N$ 個すべての区間を被覆する方法のうち、最小コストを求めよ。

制約

$1 \le N \le 100$
$1 \le D_{i}, L_{j} \le 10^{5}$
$1 \le K_{1}, K_{2} \le 1000$

考えたこと

愚直にやると次のように考えたくなる。

dp[i][j][k] ← 被覆したい区間のうちの最初の $i$ 個を被覆する方法を考える。タイプ 1 の区間を $j$ 個、タイプ 2 の区間を $k$ 個使う場合の最小コスト

しかしこれだと TLE する。状態数が $O(NK^{2})$ あって、遷移も普通にやると $O(K)$ となるので、全体の計算量は $O(NK^{3})$ となる。

工夫

しかし、よく考えると、そもそもタイプ 1 の区間を $j$ 個、タイプ 2 の区間を $k$ 使っていると考えた時点で、コストの値は決まってしまうのだ。最小コストを求めるのに、両タイプの個数を添字に持つのは過剰だ。次のように直す。

dp[i][j][k] ← 被覆したい区間のうちの最初の $i$ 個を被覆する方法を考える。タイプ 1 の区間を $j$ 個使う場合の、タイプ 2 の区間の使用個数

タイプ 2 の区間の使用個数は添字ではなく、DP 値にしてしまう。タイプ 1 の区間の使用個数を固定したとき、「タイプ 2 の区間の使用個数」と「コスト」は綺麗に対応するため、最小コストは復元できる。

このように、DP 値を用いることで、トータルの最小コストを復元するというテクニックは、青色 Diff あたりでよく見る典型手法の一つ。

素直に実装すると、 $O(N K^{2})$ の計算量となる。なお、 $O(N + K^{2})$ や $O(NK)$ の解法もあるようだ。

コード

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

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<long long> D(N);
    for (int i = 0; i < N; ++i) cin >> D[i];
    vector<long long> L(2), C(2), K(2);
    for (int i = 0; i < 2; ++i) cin >> L[i] >> C[i] >> K[i];
    
    const long long INF = 1LL<<60;
    vector<vector<long long>> dp(N+1, vector<long long>(K[0]+1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k <= K[0]; ++k) {
            for (int ak = 0; k + ak <= K[0]; ++ak) {
                long long rem = D[i] - L[0] * ak;
                long long need = 0;
                if (rem > 0) need = (rem + L[1] - 1) / L[1];
                chmin(dp[i+1][k+ak], dp[i][k] + need);
            }
        }
    }
    long long res = INF;
    for (int k = 0; k <= K[0]; ++k) {
        if (dp[N][k] <= K[1]) chmin(res, C[0]*k + C[1]*dp[N][k]);
    }
    cout << (res < INF ? res : -1) << endl;
}