📘题解说明（动态规划思想）

🔍定义

我们可以使用**动态规划（DP）**来解决：

设状态：

$dp[i][k]$ 表示前 $i$ 个位置，最多保留 $k$ 个高峰所需最小代价（体积）$；

🚧转移方程 对于第 $i$ 个位置，我们枚举可能把第 $j$ 到 $i$ 的区间保留为一个高峰，判断其合法性，然后转移为：

𝑑 𝑝 [ 𝑖 ] [ 𝑘 ]

min ⁡ 𝑗 < 𝑖 ( 𝑑 𝑝 [ 𝑗 ] [ 𝑘 − 1 ] + flatten_cost ( 𝑗 + 1 , 𝑖 ) ) $ dp[i][k]= j<i min ​ (dp[j][k−1]+flatten_cost(j+1,i))$ 其中：

flatten_cost：将第 $j+1$ 到 $i$ 区间转成一个合法高峰所需代价

要求该区间边界两边比该高峰低（否则不合法）

💡优化

由于 $N \leq 1000, K \leq 25$，该方法是可行的。 可以提前预处理任意区间 flatten 的最小代价。

📌总结

难点在于识别“高峰”的定义；

状态转移需要枚举每一个可能形成的高峰区间；

动态规划在小规模约束下是可行的；

注意不能升高，只能降低。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e3+9;
int a[maxn];
int n,k;
int work()
{
	int ans=1e9,front,end;
	int flag=1;
	for(int i=1;i<=n;i++)
	{
		if(flag&&a[i]>a[i+1])
		{
			int t=flag,s=i;
			while(t>=1&&a[t]>=a[t-1]) t--;
			while(s<=n&&a[s]>=a[s+1]) s++;
			if(t>=1||s<=n)
			{
				int sum=0,tmp=max(a[t],a[s]);
				for(int j=t+1;j<s;j++)
					if(a[j]>tmp)
						sum+=a[j]-tmp;
				if(sum<ans)
				{
					ans=sum;
					front=t+1;
					end=s-1;
				}
			}
		}
		if(a[i+1]<a[i]) flag=false;
		if(a[i+1]>a[i]) flag=i+1;
	}
	
	int tmp=max(a[front-1],a[end+1]);
	for(int j=front;j<=end;j++)
		if(a[j]>tmp)
			a[j]=tmp;
	return ans;
}


int main()
{
//    freopen("in.txt","r",stdin);
	while(scanf("%d %d",&n,&k)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		a[n+1]=0;
		int sum=0;
		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			if(flag&&a[i]>a[i+1]) sum++;
			if(a[i+1]<a[i]) flag=false;
			if(a[i+1]>a[i]) flag=true;
		}
		int ans=0;
		for(int i=sum;i>k;i--)
			ans+=work();
		cout<<ans<<endl;
	}
	return 0;
}