/*莫名其妙就做了集训队的题 不过..数据好水 codevs 1342 哈哈哈乱搞85 贪心的(好像有bug2333)照起点和终点然后dp搞答案 这个应该很简单的要滚一下数组 同桌打的暴力dp 55好像 思路一样的就是省去了那个正确性不一定的贪心 */#include<cstdio> #include<cstring>#define maxn 200010using namespace std;int n,m,f[2][maxn][2],a[maxn],c[maxn],mx,p;int init(){    int x=0,f=1;char s=getchar();    while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x*f;}int min(int x,int y){    return x<y?x:y;}int max(int x,int y){    return x>y?x:y;}int main(){    freopen("nt2011_tree.in","r",stdin);    freopen("nt2011_tree.out","w",stdout);    n=init();m=init();    memset(f,-127/3,sizeof(f));    mx=f[0][0][0];    if(n<m*2){        printf("Error!\n");        return 0;    }    for(int i=1;i<=n;i++)        a[i]=init();    a[0]=a[n];    for(int i=1;i<=n;i++)        if(a[i]-a[i-1]>mx){            mx=a[i]-a[i-1];p=i;        }    for(int i=1,x=p;i<=n;i++,x++){        if(x>n)x=1;        c[i]=a[x];    }    f[0][0][0]=0;    for(int i=1;i<=n;i++){        int x=min(m,i+1>>1);        for(int j=0;j<=x;j++){            f[i&1][j][0]=max(f[i-1&1][j][0],f[i-1&1][j][1]);            if(j)f[i&1][j][1]=f[i-1&1][j-1][0]+c[i];        }        for(int j=0;j<=x;j++){            f[i-1&1][j][0]=f[0][0][0];            f[i-1&1][j][1]=f[0][0][0];        }    }    printf("%d\n",f[n&1][m][0]);    return 0;}

/*上面那个乱搞的贪心+dp似乎有漏洞但是数据略水 也可能是能证明他正确懒得证了 说说正解吧神贪心题 Orz想出正解的首先如果不限制相邻的不能种 那就easy了那怎么保证选了之后边上的也不能选呢那就删了喽那又有个问题 万一两边的和比中间那个大咋办很神奇的做法 删了两边的之后 把中间的改成A+C-B就是两边的权值和减去中间的 这样我们在选这个新的的时候 就相当于选了两边的两个并且保证了左边的左边和右边的右边不选删了还有个很好的性质就是 选中间那个和选新构造的那个相当于选了两次 和选两边的完全一样 嗯 非常好啊然后搞个链表 再搞个堆O(mlogn) */#include<cstdio>#include<cstring>#include<queue>#define maxn 200010using namespace std;int n,m,a[maxn],l[maxn],r[maxn],ans;bool f[maxn];struct node{    int v,p;    bool operator < (const node &x) const{        return v<x.v;    }};priority_queue<node>q;int init(){    int x=0,f=1;char s=getchar();    while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x*f;}int min(int x,int y){    return x<y?x:y;}int max(int x,int y){    return x>y?x:y;}int main(){    freopen("nt2011_tree.in","r",stdin);    freopen("nt2011_tree.out","w",stdout);    n=init();m=init();    if(n<m*2){        printf("Error!\n");        return 0;    }    for(int i=1;i<=n;i++){        a[i]=init();        q.push((node){a[i],i});        l[i]=i-1;r[i]=i+1;    }    l[1]=n;r[n]=1;    while(m--){        while(f[q.top().p]&&!q.empty())q.pop();        node x=q.top();q.pop();ans+=x.v;        int L=l[x.p],R=r[x.p];        l[x.p]=l[L];r[x.p]=r[R];        r[l[L]]=x.p;l[r[R]]=x.p;        f[L]=1;f[R]=1;a[x.p]=a[L]+a[R]-a[x.p];        q.push((node){a[x.p],x.p});    }    printf("%d\n",ans);    return 0;}