题意：
给出一个长度为N的数列a，有一些操作，每次操作选择一个数，使得其最终只剩下一个数：
1、选择左端/右端，删去这个数
2、选中中间的一个数，将其值替换为左右两边的数之和，然后删去左右两边的数。
现在要求使得最终的值尽可能大，求最大的值以及操作次数，选数方案（选数方案为）。
N≤1000，a数组可能有负数N≤1000，a数组可能有负数
分析：
很直观的一点是：最终剩下的数，一定是初始状态下一些数的和。
现在有一个很特殊的性质：
设最终的数为x(x=ai1+ai2+ai3+……+aik)x(x=ai1+ai2+ai3+……+aik)
必须满足i1≡i2≡i3≡……≡ik(mod 2)i1≡i2≡i3≡……≡ik(mod2)。
并且，任意一组下标满足该条件的数集，均能构造出最终的x
证明如下：
若使用1操作，删去左端，所有下标奇偶性反转，原来奇偶性相同的现在仍然相同，删去右端，所有下标无影响。
若使用2操作，设选中的数为aiai
我们可以看做：
在ai?1ai?1的位置加上ai+1ai+1的值，并且删去ai,ai+1ai,ai+1
这样一来，在i?1i?1以前的位置，下标的奇偶性不发生改变，在i+1i+1以后的位置，因为同时删去2个数，所以下标的奇偶性仍然无影响。并且，因为i?1与i+1i?1与i+1奇偶性相同，我们将二者的值加在一起，不会使得我们最终的数集中的奇偶性不同。
现在证明“任意一组下标满足该条件的数集，均能构造出最终的x”
我们设数集中某两个的相邻数为ai,aj(i<j)ai,aj(i<j)
由j≡i(mod 2)j≡i(mod2)可得，j?i?1≡1(mod 2)j?i?1≡1(mod2)
这句话是指，任意两个相邻数之间的数的个数，一定为奇数。
这样的话，我么可以在中间做j?i?22j?i?22次2操作，再做1次1操作，就能将这两个数合并，并且将中间的数全部删去。
对数集中所有相邻的数都做一次，就能最终变为1个数。
现在答案就很好求了，我们只需要统计在奇数位置上所有非负数的和，以及偶数位置上所有非负数的和，比较大小来选择即可。
对于如何求出答案，其实在刚才的证明中已经能够看出来了。只不过官方题解给了一个更直接的方式：
首先我们将所有最终数集中的数标号，
从前向后依次查找：
若当前的数：
A、不为端点：
其两侧均无标记，或两侧均有标记，则选择这个数，
B、为端点：
若该数未标记，选择这个数
重复这个过程直到为1个数为止。由于是从前往后依次查找，并且每找一次就重来，所以其实本质上和我写的是一样的。
当然，对于所有数都是负数的情况，我们需要特判。因为我们最开始选数的时候，选择的都是非负数，若均为负数，则我们不可能选中任何一个数。相当于最终集合为空集，不合法。这个特判很好写，找到最大值，删去前面和后面的点即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1010
using namespace std;
long long a[MAXN],a1[MAXN],n,sum[2],used[MAXN],flag,r[MAXN],l[MAXN];
bool dele[MAXN];
vector<int> ans;
void del(int x){ans.push_back(x+1);a[x]=0;memset(dele,0,sizeof dele);memset(used,0,sizeof used);if(x!=0){dele[x-1]=1;a[x]+=a[x-1];}if(x!=n-1){dele[x+1]=1;a[x]+=a[x+1];}for(int i=0;i<n;i++)a1[i]=a[i];int cnt=0;for(int i=0;i<n;i++)if(dele[i]==0)a[cnt++]=a1[i];for(int i=0;i<n;i++)if(a[i]>0&&flag==i%2)used[i]=1;n=cnt;
}
void work(){int maxid=0;for(int i=0;i<n;i++)if(a[i]>a[maxid])maxid=i;PF("%lld\n%d\n",a[maxid],n-1);int sum=n;for(int i=0;i<maxid;i++){PF("%d\n",1);sum--;}for(int i=n-1;i>maxid;i--){PF("%d\n",sum);sum--;}
}
int main(){SF("%d",&n);for(int i=0;i<n;i++)SF("%lld",&a[i]);for(int i=0;i<n;i++)if(a[i]>0)sum[i%2]+=a[i];if(sum[0]==0&&sum[1]==0){work();return 0;}if(sum[0]>sum[1])flag=0;elseflag=1;for(int i=0;i<n;i++){l[i]=i-1;r[i]=i+1;}for(int i=0;i<n;i++)if(a[i]>0&&flag==i%2)used[i]=1;while(n>1){/*for(int i=0;i<n;i++)PF("{%d}",used[i]);PF("\n");*/for(int i=0;i<n;i++){if(i==0||i==n-1){if(used[i]==0){if(i==0)flag^=1;del(i);break;}}else if(used[i-1]==used[i+1]){del(i);break;}}}PF("%lld\n%d\n",a[0],ans.size());for(int i=0;i<ans.size();i++)PF("%d\n",ans[i]);
}