#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> #define int long long #define double long double #define pii pair<int, int> #define tiii tuple<int, int, int> #define tiiii tuple<int, int, int, int> #define emb emplace_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define iShowSpeed cin.tie(NULL)->sync_with_stdio(false) #define matrix vector<vector<int>> #define mat(n, m) vector<vector<int>>(n, vector<int>(m)); const int mod = 1e9+7; const int inf = 1e18; const matrix II = {{1, 0}, {0, 1}}; const int N = 1000; int n, k, a[N], dp[2][N]; struct { int seg[4 * N]; void build(int l, int r, int i){ if (l == r) return seg[i] = a[l], void(); int mid = (l + r) / 2; build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1); seg[i] = max(seg[2 * i], seg[2 * i + 1]); } int query(int l, int r, int i, int ll, int rr){ if (l >= ll && r <= rr) return seg[i]; if (r < ll || l > rr) return 0; int mid = (l + r) / 2; return max(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr)); } } seg; void dac(int l, int r, int idx, int left, int right){ if (r < l) return; int mid = (l + r) / 2; pair <int, int> ans = {inf, inf}; int mx = 0; if (right <= mid) mx = seg.query(1, n, 1, right, mid); for (int i = min(mid, right); i >= left; i--) { mx = max(mx, a[i]); ans = min(ans, {dp[(idx - 1) % 2][i - 1] + mx, i}); } // cout << idx << " : " << mid << " : " << ans.first << ", " << ans.second << "\n"; dp[idx % 2][mid] = ans.first; dac(l, mid - 1, idx, left, ans.second); dac(mid + 1, r, idx, ans.second, right); } int32_t main() { iShowSpeed; cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; seg.build(1, n, 1); for (int i = 0; i <= 1; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = inf; } } dp[0][0] = 0; for (int i = 1; i <= k; i++) { for (int j = 0; j <= n; j++) dp[i % 2][j] = inf; dac(i, n, i, i, n); // for (int j = 1; j <= n; j++) { // cout << dp[i][j] << " "; // } // cout << "\n"; } cout << dp[k % 2][n]; } /* bruteforce: dp[i][j] = min(l < j){dp[i - 1][j - 1] + cost()} */