传送门：QAQQAQ
题意：$n$个点中选$m$个不相邻的点，使得这些点不相邻（1和n算相邻），求这些点的最大值
思路：这不是神仙题不是神仙题……
刚看到这题觉得不难，好像只要贪心就可以了但贪心不知从何下手——因为取了一个点就会影响其它两个点
所以我们要用“可以反悔”的贪心，即取完一个点以后，我们要加入一个点，让此操作可以反悔——不取这个点，而取它两边的点，即$val[new]=val[l]+val[r]-val[pos]$，然后取了当前点把它左右点删去即可（因为再取一次当前点就是取它左右点的情况）（有点像网络流里的残量网络）
这样用一个堆维护，每次取最大值即可
（证明：因为有可以反悔的操作，所以每种情况都可以选到，不会因为取了当前最大值而排除了全局最优解，而每次取的都是合法的切实最大值，所以最终答案一定是最大值）
代码：（推荐比赛的时候先写一个较为稳妥的DP）
#include<bits/stdc++.h> using namespace std; const int inf=(int)2e8; const int N=200005; int dp[2][2201][1101][2]; int n,m,a[N],ans=-inf; void checkmax(int &x,int y) { if(x<y) x=y; } void subtask1() { for(int bl=0;bl<=1;bl++) for(int i=0;i<=n;i++) for(int j=1;j<=m;j++)//之前写成了0 for(int t=0;t<=1;t++) dp[bl][i][j][t]=-inf; dp[1][1][1][1]=a[1]; dp[0][1][0][0]=0; for(int bl=0;bl<=1;bl++) { for(int i=2;i<=n;i++) { for(int j=1;j<=m;j++) { if(!(i==n&&bl==1)) dp[bl][i][j][1]=dp[bl][i-1][j-1][0]+a[i]; dp[bl][i][j][0]=max(dp[bl][i-1][j][1],dp[bl][i-1][j][0]);//+=! if(j==m) { checkmax(ans,dp[bl][i][j][0]); checkmax(ans,dp[bl][i][j][1]); } } } } printf("%d ",ans); } struct node{ int l,r,val,id; bool operator < (const node &rhs) const{ return val<rhs.val; } }t[N]; int vis[N]; priority_queue<node> q; void subtask2() { int sum=0; for(int i=1;i<=n;i++) { t[i].l=i-1; t[i].r=i+1; t[i].val=a[i]; t[i].id=i; } t[1].l=n; t[n].r=1; for(int i=1;i<=n;i++) q.push(t[i]); for(int i=1;i<=m;i++) { while(vis[q.top().id]) q.pop(); node f=q.top(); q.pop(); //取出来的node不能直接用，因为它的l,r可能已经改变 vis[t[f.id].l]=vis[t[f.id].r]=1;//可以理解成三个点并成了一个点 sum+=f.val; t[f.id].val=t[t[f.id].l].val+t[t[f.id].r].val-t[f.id].val; t[f.id].l=t[t[f.id].l].l; t[f.id].r=t[t[f.id].r].r; t[t[f.id].r].l=f.id; t[t[f.id].l].r=f.id; q.push(t[f.id]); } cout<<sum<<endl; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(m>n/2) { puts("Error!"); return 0; } if(n<=2100) subtask1(); else subtask2(); return 0; }