首先拿到题面很容易可以想到的是状压DP，状态转移方程很容易可以推出来。
但是这么做的复杂度是\(O(n^2)\)的，只能拿到50分。
我们深入地考虑这一题的性质，我们发现，对于这个环，如果取用了上面的某一个点，那么这个点的两个邻点都不可取。
贪心地依据权值从大到小考虑，如果一个点的两个邻点加起来都不如它大的话，那么取邻点中的任意一个都不如取这个点。
如果这个点的两个邻点加一起比它大，那就考虑两种情况，一种情况是选择这个点，一种情况是选择这个点的两个邻点。
（很容易可以知道，如果两个邻点只选一个，那是一定没有选这个点优的。）
我们考虑先取了这个点，再转变为取这个点的两个邻点的情况。这种情况下，总权值就会减去这个点的权值，并且加上这个点的两个邻点的权值。
我们考虑一个有趣的性质。如果一个点的两个邻点都选取了，那么影响到的“不可被选取区域”的大小，是和三个都选是相同的。
因此，我们考虑究竟应该选取这个点还是这个点的两个邻点。我们考虑每当挖去一个点的时候，都把它的两个邻点标记为消失。
这时候对不可选取区域的影响已经确定了，因此只要确定对对权值的影响。
那么我们考虑建一个虚点，替代在贪心选取的那个点以及两个相邻的位置。这个虚点的权值相当于邻点的权值和减去原点的权值。
对于这个虚点，我们把它当做这个环上本来就存在的一个点来处理即可。
所以可以考虑用堆+双向链表来维护。
顺便提一句，这是一道三倍经验题，它的亲人们：
lp3620 APIO/CTSC2007 数据备份，lp1484 种树
前者只要差分一下，边转点，改大小判断以后的边界，再改一下单调队列；后者只要判一下负数情况。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,a[200005],l[200005],r[200005],nw,nw2;
bool ext[200005];
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
q.push((pii){a[i],i});
ext[i]=0;
}
if(m>(n>>1)){
puts("Error!");
return;
}
for(int i=2;i<=n;++i){
l[i]=i-1;
}
l[1]=n;
for(int i=1;i<n;++i){
r[i]=i+1;
}
r[n]=1;
long long ans=0;
for(int i=1;i<=m;++i){
while(!q.empty()&&ext[q.top().second]){
q.pop();
}
nw=q.top().second;
ans+=q.top().first;
ext[l[nw]]=1,ext[r[nw]]=1;
nw2=a[l[nw]]+a[r[nw]]-q.top().first;
a[nw]=nw2;
l[nw]=l[l[nw]],r[nw]=r[r[nw]];
r[l[nw]]=nw,l[r[nw]]=nw;
q.pop();
q.push((pii){nw2,nw});
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}顺便贴一下后面两题的代码：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,a[500005],l[500005],r[500005],nw,nw2;
bool ext[500005];
//lp1484 种树
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
q.push((pii){a[i],i});
ext[i]=0;
}
if(m>(n>>1)){
puts("Error!");
return;
}
for(int i=1;i<=n;++i){
l[i]=i-1;
}
for(int i=1;i<=n;++i){
r[i]=i+1;
}
long long ans=0;
for(int i=1;i<=m;++i){
while(!q.empty()&&ext[q.top().second]){
q.pop();
}
if(q.top().first<0){
break;
}
nw=q.top().second;
ans+=q.top().first;
ext[l[nw]]=1,ext[r[nw]]=1;
nw2=a[l[nw]]+a[r[nw]]-q.top().first;
a[nw]=nw2;
l[nw]=l[l[nw]],r[nw]=r[r[nw]];
r[l[nw]]=nw,l[r[nw]]=nw;
q.pop();
q.push((pii){nw2,nw});
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,a[100005],l[100005],r[100005],nw,nw2;
bool ext[100005];
//lp3620 APIOCTSC2007 数据备份
typedef pair<int,int> pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
ext[i]=0;
}
for(int i=n;i>=1;--i){
a[i]-=a[i-1];
}
for(int i=1;i<n;++i){
a[i]=a[i+1];
q.push((pii){a[i],i});
}
a[0]=a[n]=0x3f3f3f3f;
if(m>(n>>1)){
puts("Error!");
return;
}
for(int i=1;i<n;++i){
l[i]=i-1;
}
for(int i=1;i<n;++i){
r[i]=i+1;
}
long long ans=0;
for(int i=1;i<=m;++i){
while(!q.empty()&&ext[q.top().second]){
q.pop();
}
nw=q.top().second;
ans+=q.top().first;
ext[l[nw]]=1,ext[r[nw]]=1;
nw2=a[l[nw]]+a[r[nw]]-q.top().first;
a[nw]=nw2;
l[nw]=l[l[nw]],r[nw]=r[r[nw]];
r[l[nw]]=nw,l[r[nw]]=nw;
q.pop();
q.push((pii){nw2,nw});
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}