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';
}