正解:贪心
解题报告:
$umm$感觉这种问题还蛮经典的,,,就选了某个就不能选另一个这样儿,就可以用堆模拟反悔操作
举个$eg$,如果提出了$a_i$,那就$a_{i-1}$和$a_{i+1}$都不能选了,所以如果选了$a_i$之后想反悔选$a_{i-1}$和$a_{i+1}$就相当于只能另外获得$a_{i+1}+a_{i-1}-a_{i}$的收益了.所以每次取出堆顶$a_{i}$之后,就把$a_{i-1}$和$a_{i+1}$删了,然后插入$a_{i-1}+a_{i+1}-a_{i}$.然后多个数也差不多$QwQ$
所以就用个堆+链表维护下就成$QwQ$
$over$
#include<bits/stdc++.h> using namespace std; #define il inline #define gc getchar() #define ll long long #define ri register int #define rb register bool #define rc register char #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) #define lb(x) lower_bound(st+1,st+st_cnt+1,x)-st const int N=500000+10,inf=1e9; int n,K,a[N],l[N],r[N],d[N]; ll as; bool vis[N]; struct node{ll dat;int id;}tmp; priority_queue<node>Q; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il bool operator < (node gd,node gs){return gd.dat>gs.dat;} int main() { //freopen("3620.in","r",stdin);freopen("3620.out","w",stdout); n=read();K=read(); rp(i,0,n-1){d[i]=read();if(i){tmp=(node){a[i]=d[i]-d[i-1],i};Q.push(tmp);l[i]=i-1;r[i]=i+1;}} r[0]=1;l[n]=n-1;a[0]=a[n]=inf; while(K--) { while(vis[Q.top().id])Q.pop(); node nw=Q.top();Q.pop();ri pos=nw.id; as+=nw.dat;nw.dat=a[pos]=a[l[pos]]+a[r[pos]]-a[pos];Q.push(nw); vis[l[pos]]=vis[r[pos]]=1;l[pos]=l[l[pos]];r[pos]=r[r[pos]];r[l[pos]]=pos;l[r[pos]]=pos; } printf("%lld ",as); return 0; }