2799. 区间覆盖

#include "bits/stdc++.h"

using namespace std;

static inline void optimize_cxx_io() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
using u32 = uint32_t;
using u64 = uint64_t;

/**
 * Make indices start from 1;
 *
 * let w(i, j) = min cost to cover all points in i..=j; // Note the inclusive. Thus w(i, i) contains one point, no
 *                                                      // corner cases.
 *
 * let dp(i, j) = min cost to cover exactly j points in 1..=i;
 *   Invariant: i >= j;
 *
 * initialize dp(i, j) to a number large enough (`kInf`, denoting "impossible");
 *
 * dp(i, 0) = 0 for any i;
 *
 * dp(i, j) = min {
 *   dp(i - 1, j) if i > j;                                 // not choose the last point.
 *   dp(i - k, j - k) + w(i - k + 1, i) for all k in 1..=j; // choose the last k points.
 * }
 *
 * Since the question asks for *at least*, not exactly,
 * output min of dp(n, k) for all k in kMinNum..=n;
 */
int main() {
  optimize_cxx_io();

  u32 t;
  cin >> t;
  for (u32 _ = 0; _ != t; ++_) {
    cout << "case #" << _ << ":\n";

    u32 n, m, k;
    cin >> n >> m >> k;
    u64 constexpr static kMaxWeight = 1000000000;
    u64 constexpr static kInf = numeric_limits<u64>::max() / 2 - kMaxWeight;
    vector<vector<u64>> w(n + 1, vector<u64>(n + 1, kInf));
    vector<vector<u64>> dp(n + 1, vector<u64>(n + 1, kInf));
    for (auto& i : dp) {
      i[0] = 0;
    }

    for (u32 i = 0; i != m; ++i) {
      u32 l, r, cost;
      cin >> l >> r >> cost;
      for (u32 j = l, j_end = r + 1; j != j_end; ++j) {
        if (w[j][r] > cost) {
          w[j][r] = cost;
        }
      }
    }

    for (u32 i = 1, i_end = n + 1; i != i_end; ++i) {
      for (u32 j = 1; j != i; ++j) {
        dp[i][j] = dp[i - 1][j];
        for (u32 u = 1, u_end = j + 1; u != u_end; ++u) {
          auto tmp = dp[i - u][j - u] + w[i - u + 1][i];
          if (dp[i][j] > tmp) {
            dp[i][j] = tmp;
          }
        }
      }
    }

    auto ans = *min_element(&dp[n][k], &*dp[n].end());
    if (ans == kInf) {
      cout << "-1\n";
    } else {
      cout << ans << '\n';
    }
  }

}