首先做一次差分就可以划归到 $n$ 选 $k$ 互不相邻，求和的最小值。

思路是对每一个数加上一个值，然后直接 dp 就可以得到最优情况下选了多少个数。

然而这个调参十分难，并且按照道理 $l,r$ 大一点应该会更好，然而调出来只有 $l=-10^{10},r=1.08\times 10^{14}$ 可以AC，十分玄学。

代码写的是求最大值，很可能写假了/kk。

这份代码虽然 AC 了，但是我还是感到疑惑，所以来提问。请各位大佬 D 爆我/kk

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,a[300005];
ll l,r,mid,num[300005],b[300005],dp[300005];
int check(__int128 x){
	//wqs t x d y ! STO wqs Orz! wqs binary search:a[i]=a[i]+mid;
	for(int i=1;i<=n;++i)b[i]=a[i]+x;
	if(b[1]>0)dp[1]=b[1],num[1]=1;
	else dp[1]=0,num[1]=0;
	for(int i=2;i<=n;i++){
		if(dp[i-1]>dp[i-2]+b[i])dp[i]=dp[i-1],num[i]=num[i-1];
		else dp[i]=dp[i-2]+b[i],num[i]=num[i-2]+1;
	}
	return num[n];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i;i--)a[i]-=a[i-1];
	for(int i=1;i<=n;i++)a[i]=0-a[i+1];n--;
	l=-1e10,r=1.08e14;
	while(l<=r){
		mid=(l+r)>>1;
		int orzwqs=check(mid);
		if(orzwqs<k)l=mid+1;
		if(orzwqs>k)r=mid-1;
		if(orzwqs==k)break;
	}
	ll x=-(dp[n]-mid*k);
	printf("%lld\n",x);
}