首先如果一条线不是了连接的相邻两个位置一定不优,把它拆成若干连接相邻位置的线.所以现在问题是有\(n\)个物品,选\(k\)个,要求选的位置不能相邻,求最小总和
如果没有选的位置不能相邻这个限制,那就每次选最小的.现在仍然考虑每次选最小的,但是会有情况是这一次取的位置不在最优方案中,那么如果是这种情况,那么一定是要把不选这个东西,选旁边两个东西.考虑保留这个决策的选择,每选一个数\(x\),就把它旁边两个数\(y,z\)和\(x\)合并成\(y+z-x\).然后所有数可以堆维护,前驱后继可以链表维护
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
const int N=1e5+10;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,kk,ft[N],nt[N];
LL ans;
struct node
{
LL x,i;
bool operator < (const node &bb) const {return x!=bb.x?x>bb.x:i>bb.i;}
bool operator == (const node &bb) const {return x==bb.x&&i==bb.i;}
}a[N];
bool ban[N];
void del(int x)
{
nt[ft[x]]=nt[x],ft[nt[x]]=ft[x];
ban[x]=1;
}
struct HEAP
{
priority_queue<node> q1;
void mntn(){while(!q1.empty()&&(ban[q1.top().i]||!(q1.top()==a[q1.top().i]))) q1.pop();}
void push(node x){q1.push(x);}
void pop(){mntn();q1.pop();}
node top(){mntn();return q1.top();}
}hp;
int main()
{
n=rd()-1,kk=rd();
nt[0]=1;
for(int i=1;i<=n+1;++i) ft[i]=i-1,nt[i]=i+1;
int las=rd();
for(int i=1;i<=n;++i)
{
int x=rd();
a[i]=(node){x-las,i};
las=x;
hp.push(a[i]);
}
a[0]=(node){1ll<<40,0},hp.push(a[0]);
a[n+1]=(node){1ll<<40,0},hp.push(a[n+1]);
while(kk--)
{
int x=hp.top().i;
hp.pop();
ans+=a[x].x;
int y=ft[x],z=nt[x];
a[x].x=a[y].x+a[z].x-a[x].x;
hp.push(a[x]);
del(y),del(z);
}
printf("%lld\n",ans);
return 0;
}