一眼 DP，准确说是资源分配类 DP。这类题目大意是有 $N$ 个资源（本题是蛇，类似还有工程项目，作业等等），要把这 $N$ 组资源分配给 $K$ 个人（本题是要分给 $K$ 个网去抓蛇），并求最值。P1854 就是一个典型的资源分配类 DP。

那么这类 DP 怎么做呢？一般分三重循环。

第一重： 循环 $i$ 表示前 $i$ 个物品

第二重： 循环 $j$ 表示现在要分配第 $j$ 组物品

第三重： 循环 $k$ 表示将编号 $k+1$ 到 $i$ 的物品分配给第 $j$ 组

状态转移方程可以归纳为

$f[i][j]=\max/\min(f[i][j], f[k][j-1]+\operatorname{value}(k+1,i,j))$

$\operatorname{value(k+1,i,j)}$ 表示编号 $k+1$ 到 $i$ 的物品分配给第 $j$ 组的价值。

本题只需要将上面的模板中 $\operatorname{value}(k+1,i,j)$ 修改一下就好了。

不难发现，本题若是将区间 $[l,r]$ 分为一组，其价值（最小浪费空间）为

$maxnum[l][r]*(r-l+1)-sum[l][r]$

$sum$ 直接前缀和处理，$maxnum$ 用 $n^2$ 扫一遍求也无伤大雅，于是可以开心的打代码了。

Code

#include <bits/stdc++.h>
#define lc(a) (a)<<1
#define rc(a) (a)<<1|1
#define ll long long
#define Mod 1000000007
#define Max 1145141919
#define LLMax 9223372036854775807
using namespace std;
inline int in(){
	char c=getchar();int f=1;int x;
	while((c<'0'||c>'9')&&c!='-') c=getchar();
	if(c=='-')f=-1,c=getchar();
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
template <typename T>
inline void in(T &x){
	char c=getchar();int f=1;
	while((c<'0'||c>'9')&&c!='-') c=getchar();
	if(c=='-')f=-1,c=getchar();
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+(c^48);
	x*=f;
}
const int N=405,M=1e3+5;
int s[N],mx[N][N],f[N][N];
int main(){
	int n=in(),m=in()+1;
	for(int i=1;i<=n;i++)
		in(mx[i][i]),s[i]=s[i-1]+mx[i][i];
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			mx[i][j]=max(mx[i][j-1],mx[j][j]);
	memset(f,0x3f,sizeof f);f[0][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m&&j<=i;j++)
			for(int k=0;k<i;k++)
				f[i][j]=min(f[i][j],f[k][j-1]+mx[k+1][i]*(i-k)-s[i]+s[k]);
	for(int i=0;i<=m;i++)
		f[n][m+1]=min(f[n][m+1],f[n][i]);
	printf("%d\n",f[n][m+1]);
	return 0;
}