We solve this problem by dynamic programming. Let $dp(m,k)$ be the minimum sum of net sizes needed to catch the first $m$ groups of snakes with $k$ net size changes. Then $dp(m,0) = m \cdot \max\{a_1, \dots, a_m\}$ and for all $k > 0$,
Naively, there are $O(N^2)$ states each with $O(N)$ transitions each computable in $O(N)$ time, but the resulting complexity of $O(N^4)$ is too slow. However, it can be improved. For each $m$ and $k$, start with $i = m-1$ and decrement down to $0$. Then $\max\{a_{i+1},\dots,a_m\}$ can be maintained with constant time work for each $i$, so the cost of computing all transitions for $dp(m,k)$ is only $O(N)$. This yields an $O(N^3)$ runtime, which is sufficient for the given bounds.
#include <iostream> #include <algorithm> using namespace std; #define INF 1000000000 int N,K; int A[401]; int dp[401][401]; int main() { cin >> N >> K; int tot = 0; int high = 0; for(int i=1;i<=N;i++) { cin >> A[i]; high = max(high, A[i]); dp[i][0] = high*i; for(int j=1;j<=K;j++) { dp[i][j] = INF; int mx = A[i]; for(int b=i-1;b>=0;b--) { dp[i][j] = min(dp[i][j], dp[b][j-1] + mx*(i-b)); mx = max(mx, A[b]); } } tot += A[i]; } cout << dp[N][K] - tot << '\n'; }