原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=2151 最容易想到的是O(n^2) dp。 这里有个优雅处理，就是当选一棵树时，删掉旁边两棵树，把旁边两棵树美观度之和减去当前树的美观度替换当前树的美观度（即a[i]:=a[left[i]]+a[right[i]]-a[i]）,这样下次如果取了这棵树就代表取旁边两棵树而不取中间那棵了。只要用堆和链表维护一下，每次取最大的美观度即可。复杂度O(nlogn) （写的时候发现堆和链表都忘光了，还忘打感叹号，调半天。。） （至于csdn上有一些代码莫名高亮我也不知道为什么）
type point=record v,p,s,i:longint; flag:boolean; end; var h:array[0..200001] of point; q:array[0..200001] of longint; n,m,i,s,ans:longint; procedure heap(p:longint); var t:point; e:longint; begin while ((p<<1<=s)and(h[p].v<h[p<<1].v))or((p<<1+1<=s)and(h[p].v<h[p<<1+1].v)) do begin if (p<<1+1<=s)and(h[p<<1].v<h[p<<1+1].v) then e:=p<<1+1 else e:=p<<1; q[h[e].i]:=p; q[h[p].i]:=e; t:=h[p];h[p]:=h[e];h[e]:=t; p:=e; end; end; procedure heap2(p:longint); var t:point; begin while (p>1)and(h[p].v>h[p>>1].v) do begin q[h[p>>1].i]:=p; q[h[p].i]:=p>>1; t:=h[p];h[p]:=h[p>>1];h[p>>1]:=t; p:=p>>1; end; end; begin read(n,m); if m<<1>n then begin writeln('Error!'); halt; end; for i:=1 to n do read(h[i].v); s:=0; for i:=1 to n do begin inc(s); q[i]:=s; if i=1 then h[s].p:=n else h[s].p:=i-1; h[s].s:=i mod n+1; h[s].i:=i; h[s].flag:=true; heap2(s); end; ans:=0; for i:=1 to m do begin while not h[1].flag do begin h[1]:=h[s]; dec(s); heap(1); end; inc(ans,h[1].v); h[1].v:=h[q[h[1].p]].v+h[q[h[1].s]].v-h[1].v; h[q[h[1].p]].flag:=false; h[q[h[1].s]].flag:=false; h[1].p:=h[q[h[1].p]].p; h[1].s:=h[q[h[1].s]].s; h[q[h[1].p]].s:=h[1].i; h[q[h[1].s]].p:=h[1].i; heap(1); end; writeln(ans); end.