// yukicodr // No.45 //二次元可変配列 //vector > mass; //vector > memo; //vector memo; //#include "stdafx.h" #include #include #include //list #include //queue #include //連想コンテナ(要素が自動でソートされる)、要素1つ(Key)、keyの重複ない、O(logN) #include //連想コンテナ(要素が自動でソートされる)、要素2つ(Key,data)、keyの重複ない、dataは重複あり、O(logN) #include //hash、O(1) #include //hash、O(1) #include #include #include //#include using namespace std; #define FOR(x,to) for(x=0;x(b)?(a):(b)) #define FMIN(a,b) ((a)<(b)?(a):(b)) #define FCEIL(a,b) ((a)+(b)-1)/(b) typedef unsigned long long ULL; typedef signed long long SLL; queue _queue; int N; int dp[1005][1005]; int V[1005]; int main() { cin >> N; for (int i = 1; i <= N; i++) { scanf("%d", &V[i]); } for (int i = 1; i <= N; i++) { dp[1][i] = V[1]; } dp[2][1] = dp[1][1]; for (int i = 1; i <= N; i++) { if (i >= 2) { dp[2][i] = FMAX(dp[1][i],V[i]); } } for (int n = 3; n <= N; n++) { for (int i = 1; i <= N; i++) { if (i>=n) { dp[n][i] = FMAX(dp[n - 1][i - 1],dp[n-1][i-2]+V[i]); } else { dp[n][i] = dp[n - 1][i]; } } } cout << dp[N][N] << endl; return 0; }