一个奇怪的取数游戏

这是NOI导刊上的一道题目，题目是这么说的：

输入N个整数（它们的范围在-1000~+1000），它们顺次围成一个环。
在这N个数中取出M个数，条件是任意两个取出的数不能相邻，求它们的和的最大值。
如果不能按要求取出M个数，则输出Error!
N的范围是[10,200000]，M一定小于N。

显然，当M > N div 2时，就不能取出M个数了，因此直接退出。

容易想到一个动态规划的解法：
用f[i][j][0]表示不取第i个数，前i个数一共取出了j个数获得的和的最大值；
用f[i][j][1]表示取第i个数，前i个数一共取出了j个数获得的和的最大值。

显然
f[i][j][0] = max{f[i - 1][j][1],f[i - 1][j][0]}
f[i][j][1] = f[i - 1][j - 1][0]
稍微处理下环和边界情况就OK了。

不过呢，这个动态规划的时间复杂度是N^2级别的，对于200000的N是显然行不通的。

==================================================

导刊上给出了一个诡异的解法，用最大堆和双向链表。
首先，用双向链表记录每个位置前后的数的位置，构成一个环形链表。
与此同时，把所有数的编号加入最大堆。
然后，进行M次如下操作：

x = heap[0]
ans += value[x]
value[x] = value[left[x]] + value[right[x]] - value[x]
维护堆
把left[x]和right[x]从堆和双向链表中删去，并维护堆。

最后输出ans

其中value[x] = value[left[x]] + value[right[x]] - value[x]这句话是最关键的，请注意里面的减号，这说明如果某个值被加到了ans里面，在后面的操作中它还有可能被再次减去。就像用Ford-Fulkerson求最大流一样，某些边的流量反而会减小，但是S到T的流量是增加的。

如果按照这个算法，这道题完全可以转化成费用流解，关于如何转化本人还要思考下。

在编写这个程序的时候还有一个小插曲，起初只通过了一半的数据，检查发现每次修改堆中数据后，必须“马上”对堆进行调整，否则会破坏堆的结构。

按照惯例，给出代码：

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 400005
#define pa(x)    (((x) - 1) / 2)
#define lc(x)    ((x) * 2 + 1)
#define rc(x)    ((x) * 2 + 2)

long N,M;
long v[MAXN],heap[MAXN],heapsize,pos[MAXN];
long l[MAXN],r[MAXN];

void moveup(long x)   //x:the index in heap
{
   long tmp;
   while(x > 0 && v[heap[x]] > v[heap[pa(x)]])
   {
       tmp = heap[x];
       heap[x] = heap[pa(x)];
       heap[pa(x)] = tmp;
       tmp = pos[heap[x]];
       pos[heap[x]] = pos[heap[pa(x)]];
       pos[heap[pa(x)]] = tmp;
       x = pa(x);
   }
}

void movedown(long x)
{
   long s,tmp;
   s = x;
   while(1)
   {
       if(lc(x) < heapsize && v[heap[lc(x)]] > v[heap[s]])    s = lc(x);
       if(rc(x) < heapsize && v[heap[rc(x)]] > v[heap[s]])    s = rc(x);
       if(s != x)
       {
           tmp = heap[x];
           heap[x] = heap[s];
           heap[s] = tmp;
           tmp = pos[heap[x]];
           pos[heap[x]] = pos[heap[s]];
           pos[heap[s]] = tmp;
           x = s;
       }
       else break;
   }
}

int main()
{
   freopen("compile.in","r",stdin);
   freopen("compile.out","w",stdout);
   scanf("%ld%ld",&N,&M);
   if(M > N / 2)
   {
       printf("Error!\n");
       fclose(stdout);
       exit(0);
   }
   long i;
   long ans = 0;
   heapsize = 0;
   for(i = 0;i < N;i ++)
   {
       scanf("%ld",&v[i]);
       heap[heapsize] = i;
       pos[i] = heapsize;
       moveup(heapsize);
       heapsize ++;
       l[i] = i - 1;
       r[i] = i + 1;
   }
   l[0] = N - 1;
   r[N - 1] = 0;
   while(M --)
   {
       i = heap[0];
       ans += v[i];
       v[i] = v[l[i]] + v[r[i]] - v[i];
       movedown(0);
       v[l[i]] = -1000000000;    //same effect as removal
       movedown(pos[l[i]]);
       v[r[i]] = -1000000000;
       movedown(pos[r[i]]);
       l[i] = l[l[i]];
       r[i] = r[r[i]];
       l[r[i]] = i;
       r[l[i]] = i;
   }
   printf("%ld\n",ans);
   fclose(stdout);
   return 0;
}