DP を用いて解くことを考えます。一番簡単に思いつくのは「何個目の区間まで見たか」「センサー \(1\) を何個使ったか」「センサー \(2\) を何個使ったか」をキーとして持つ DP ですが、これでは実行時間制限に間に合いません。ここで、今までに使ったセンサー \(1\) の個数が固定されているとき、使ったセンサー \(2\) の個数は最小のもの以外考える必要がないことから、以下のような DP が自然に導出されます。

\[dp[i][j] =(i\text{ 個目の区間まで見て、使ったセンサー }1\text{ の個数が }j\text{ であるときの、使ったセンサー }2\text{ の個数の最小値})\]

遷移は、\(i\) 個目の区間を監視するために使うセンサー \(1\) の個数を全探索することで、

\[dp[i][j] = \min_{0 \leq k \leq j} \bigg(dp[i-1][j-k] + \Big\lceil \frac{\max(D_i-kL_1,0)}{L_2} \Big\rceil \bigg)\]

となります。状態が \(O(NK_1)\)、遷移が \(O(K_1)\) なので全体の計算量は \(O(NK_1^2)\) となり、十分高速です。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (int &i: d) cin >> i;
    vector<int> l(2), c(2), k(2);
    for (int i = 0; i < 2; i++) {
        cin >> l[i] >> c[i] >> k[i];
    }
    vector dp(n + 1, vector<int>(k[0] + 1, 1e9));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k[0]; j++) {
            int rem = d[i];
            for (int nj = j; nj <= k[0]; nj++) {
                dp[i + 1][nj] = min(dp[i + 1][nj], dp[i][j] + (rem + l[1] - 1) / l[1]);
                rem = max(rem - l[0], 0);
            }
        }
    }
    ll ans = 2e18;
    for (int i = 0; i <= k[0]; i++) {
        if (dp[n][i] > k[1]) continue;
        ans = min(ans, (ll) c[0] * i + (ll) c[1] * dp[n][i]);
    }
    if (ans > 1e18) ans = -1;
    cout << ans << endl;
}