Make Breads

2 secs 1024 MB

dyktr_06

Problem

Submissions

Test cases

Editorial

$dp[i][j] :$ 区間 $[i, j]$ を合成するために必要なスタミナの最小値
という動的計画法を考えます。

区間の範囲 $d$ を広げながら遷移を行うことで正しく計算することができます。(詳しくは実装例を参照してください。)

あらかじめ累積和を計算しておくことによって、動的計画法を計算を $O(N^3)$ で計算することができます。

あとは、区間の和が $K$ 以上になっている区間においての DP テーブルの最小値を出力すればよいです。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

const long long INF = 0x1fffffffffffffff;

int main(){
    long long n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            dp[i][j] = INF;
        }
    }

    vector<long long> sum(n + 1);
    for(int i = 0; i < n; i++){
        sum[i + 1] = sum[i] + a[i];
    } 

    for(int d = 1; d < n; d++){
        for(int i = 0; i < n; i++){
            int l = i, r = l + d;
            if(r >= n) continue;
            for(int j = l + 1; j <= r; j++){
                dp[l][r] = min(dp[l][r], dp[l][j - 1] + dp[j][r] + abs((sum[j] - sum[l] - sum[r + 1] + sum[j])));
            }
        }
    }

    long long ans = INF;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            if(sum[j + 1] - sum[i] >= k){
                ans = min(ans, dp[i][j]);
            }
        }
    }
    if(ans == INF){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
}