#include #include #include #include #include #include #include #include #include // require sort next_permutation count __gcd reverse etc. #include // require abs exit atof atoi #include // require scanf printf #include #include // require accumulate #include // require fabs #include #include #include #include // require setw #include // require stringstream #include // require memset #include // require tolower, toupper #include // require freopen #include // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() /* No.45 回転寿司 DP解 dp[0] = 0; dp[1] = v[1]; dp[i] = max (dp[i-1], dp[i-2] + v[i] ); (i >= 2 ) */ using namespace std; typedef long long ll; typedef pair P; const int MAX_N = 1005; int dp[MAX_N]; int V[MAX_N]; int main() { memset (dp, 0, sizeof (dp ) ); memset (V, 0, sizeof (V ) ); ios_base::sync_with_stdio(0); int N; cin >> N; for (int i = 1; i <= N; i++ ) cin >> V[i]; dp[1] = V[1]; for (int i = 2; i <= N; i++ ){ dp[i] = max (dp[i-1], dp[i-2] + V[i] ); } // end for cout << dp[N] << endl; return 0; }