#include<iostream> #include<vector> #include<algorithm> #include<string> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<unordered_map> #include<unordered_set> using namespace std; using ll = long long; ll mod = 1e9 + 7; ll gcd(ll a, ll b) { if (b == 0)return a; else return gcd(b, a % b); } bool check(string s, string t) { ll i = 0, j = 0; while (i < s.size() && j < t.size()) { if (s[i] == t[j]) { j++; } i++; } if (j == t.size())return 1; else return 0; } void solve() { ll n, k; cin >> n >> k; vector<ll>v(n + 1); for (ll i = 1; i <= n; i++) { cin >> v[i]; } stack<pair<ll, ll>>st; vector<ll>mec(n + 1, 0); for (ll i = 1; i <= n; i++) { while (st.size()&&st.top().first <= v[i]) { st.pop(); } if (st.size()) { mec[i] = st.top().second; } st.push({ v[i],i }); } //for (ll i = 1; i <= n; i++)cout << mec[i] << " "; //cout << endl; vector<vector<ll>>dp(n + 1, vector<ll>(k + 1, 1e18)); dp[0][0] = 0; for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= k; j++) { ll urde = mec[i]; dp[i][j] = min(dp[i][j], dp[max(j-1,urde)][j - 1] + v[i]); dp[i][j] = min(dp[i][j], dp[urde][j]); } } cout << dp[n][k] << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); ll t = 1; //cin >> t; while (t--) { solve(); } }