可以发现，选的电缆越多，权值和越大，并且斜率呈单调递增，图像是一个下凸壳的形式

那么我们就可以\(\rm wqs\)二分解决这个问题

二分斜率，我们就可以去掉那个\(k\)的限制

设\(f[i][0/1]\)表示前\(i\)个数，第\(i\)个数选/不选的最小代价

由贪心可知，我们选的电缆一定是相邻的

所以就可以愉快的写出代码了

#include
    
     #include
     
      #include
      
       using namespace std;#define rg register#define int long longvoid read(int &x){    char ch;bool ok;    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());    if(ok)x=-x;}const int maxn=1e5+10;int n,k,a[maxn],b[maxn],sum,ans;struct oo{int x,y;}f[maxn][2];bool check(int x){    for(rg int i=2;i<=n;i++){        if(f[i-1][1].y
       
        f[i-1][0].y)f[i][0]=f[i-1][0];        else if(f[i-1][1].x>f[i-1][0].x)f[i][0]=f[i-1][0];        else f[i][0]=f[i-1][1];        f[i][1]=(oo){f[i-1][0].x+1,f[i-1][0].y+a[i]-a[i-1]-x};    }    oo now;    if(f[n][0].y
        
         f[n][1].y)now=f[n][1];    else if(f[n][0].x>f[n][1].x)now=f[n][1];    else now=f[n][0];    if(now.x<=k)return sum=now.y,1;    else return 0;}signed main(){    read(n),read(k);int l=0,r=0;    for(rg int i=1;i<=n;i++)read(a[i]),r+=a[i];    while(l<=r){        int mid=(l+r)>>1;        if(check(mid))l=mid+1,ans=sum+mid*k;        else r=mid-1;    }    printf("%lld\n",ans);}