#include /* ルールの説明がわかりにくいが、 間を1個以上開けた上昇列として指定し、 和が最大になるようにする*/ /* 間は1個開けるか2個開けるかどっちか。 なぜなら、3つ以上開ける時、その真ん中にあるやつを他を変えずに取れるから。*/ /* 最初の2個のうち、どちらかはとることになる*/ /* 寿司の基本定理 -*-の方が*-*より大きい ならば真ん中は必ず採用 */ /* *--*-*-*-*-*-*--* *-*-*-*-*-*-*-*-* 2空けが2回以上出てくる時、 必ずこのパターン。 */ /* *-*-*--*-*-*--* *-*-*-*-*-*-*-* *--*-*-*--* *-*-*-*-*-* *--*-*--*--* *-*-*-*-* *--*-*--* *-*-*-* *--*--* *-*-*-*-* *--*-*--* */ int mymax(int a, int b); int sum_1step(int *V, int s, int e); int main(void){ int i, j, N, M, all1, two2, s1, start, end, s=0, temp=0, t=0; scanf("%d", &N); int V[N+4]; V[0]=0; V[1]=0; V[N+2]=0; V[N+3]=0; for(i=2;i<=N+1;i++) scanf("%d", V+i); start=0; end=1; for(end=start+6;end<=N+3 && !(end==N+2);end+=2){ for(s1=start;s1+6<=end;s1+=2){ all1=sum_1step(V, s1+2, end-2); two2=sum_1step(V, s1+3, end-3); if(two2>all1){ s+=sum_1step(V, start, s1); start=s1+3; end=start+4; break; } } } end=N+3; //startは生きてる。 if((M=end-start+1)%2==0){//この時2の間隔がちょうど一個 for(j=1;j<=M/2-1;j++){ temp=sum_1step(V, start, start+(j-1)*2);//jは間隔が2になる以前の個数 temp+=sum_1step(V, start+(j-1)*2+3, end); t=mymax(t, temp); } s+=t; printf("%d\n", s); } else{ //この時あとは2の間隔なし s+=sum_1step(V, start, end); printf("%d\n", s); } return 0; } int mymax(int a, int b){ if(a>b) return a; else return b; } int sum_1step(int *V, int s, int e){ int i, sum=0; for(i=s;i<=e;i+=2) sum+=V[i]; return sum; }