题意

给你一个地图，让你将山峰调整到 $k$ 个。

思路

贪心。

我们先计算已有的山峰个数，再寻找体积最小的山挖掉，然后更新状态。

可以用一个结构体来存储山。为了方便计算可以写 calc 函数计算体积。

实现

千万不要像我一样没有判不用砍的情况。

关于峰可以用上下边界判断。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
struct hill
{
	int l,r,h,v;
}a[N];
int n,k,h[N],cnt,res;
bool st[N];
void calc(int l,int r,int p)
{
	a[p] = {l,r,max(h[l],h[r]),0};
	for(int i = l; i <= r; i ++)
		if(h[i] > a[p].h) a[p].v += h[i] - a[p].h;
}
void get_h(int p)
{
	int l = a[p].l,r = a[p].r;
	while(l >= 1 && h[l - 1] <= h[l]) l --;
	while(r <= n && h[r + 1] <= h[r]) r ++;
	calc(l,r,p);
}
int main()
{
	cin>>n>>k;
	for(int i = 1; i <= n; i ++) cin>>h[i];
	for(int i = 1; i <= n; i ++)
		if(!st[i])
		{
			st[i] = 1;
			int l = i,r = i;
			bool fl = 0,fr = 0;
			while(l >= 1 && h[l - 1] <= h[l]) l --,st[l] = 1,fl |= (h[l] < h[i]);
			while(r <= n && h[r + 1] <= h[r]) r ++,st[r] = 1,fr |= (h[r] < h[i]);
			if(fl && fr) calc(l,r,++ cnt);
		}
	int hs = cnt;
	memset(st,0,sizeof st);
	while(hs > k)
	{
		int minv = 2e9,p = 0;
		for(int i = 1; i <= cnt; i ++)
			if(!st[i] && a[i].v < minv) minv = a[i].v,p = i;
		res += minv,st[p] = 1;
		hs --;
		for(int i = a[p].l; i <= a[p].r; i ++) h[i] = min(h[i],a[p].h);
		for(int i = 1; i <= cnt; i ++)
			if(!st[i]) get_h(i);
	}
	printf("%d\n",res);
	return 0;
}