#include /* ルールの説明がわかりにくいが、 間を1個以上開けた上昇列として指定し、 和が最大になるようにする*/ /* 間は1個開けるか2個開けるかどっちか。 なぜなら、3つ以上開ける時、その真ん中にあるやつを他を変えずに取れるから。*/ /* 最初の2個のうち、どちらかはとることになる*/ /* 寿司の基本定理 -*-の方が*-*より大きい ならば真ん中は必ず採用 */ int mymax(int a, int b); int maxsushi(int *V, int *Memo, int i, int N); /* Vは配列、i, NはV[i]からV[i+N-1]の最大値を計算せよというindexと残り個数 Memoは、iから先の最大値が既に計算してあれば、Memo[i]にその最大値が入っている VとMemoは同じサイズの配列だと仮定している。*/ int main(void){ int i, N; scanf("%d", &N); int V[N], Memo[N]; for(i=0;ib) return a; else return b; } int maxsushi(int *V, int *Memo, int i, int N){ if(N<=0) return 0; else if(N==1) return *(V+i); else if(N==2){ if(Memo[i]<0) Memo[i]=mymax(*(V+i), *(V+i+1)); return Memo[i]; } else{ if(Memo[i]<0) Memo[i]=mymax((*(V+i))+maxsushi(V, Memo, i+2, N-2), (*(V+i+1))+maxsushi(V, Memo, i+3, N-3)); return Memo[i]; } }