/* * main.cpp * * Created on: 2017/10/06 * Author: sep */ #include #include #include #include #include #include #include #include #include #include using namespace std; inline int main003(); inline int main045(); inline int main3(); inline int main4(); #define TEST int main() { #ifdef TEST while (1) #endif main045(); return 0; } inline int get_bit(int x) { int c = 0; while (x) { if (x & 1) c++; x >>= 1; } return c; } inline int main003() { int num; int route, v1, v2, bit_count; int result = 0; map v; queue q; cin >> num; q.push(1); v[1] = 1; while (!q.empty()) { route = q.front(); q.pop(); if (route == num) { result = v[route]; break; } bit_count = get_bit(route); v1 = route + bit_count; v2 = route - bit_count; if ((v1 <= num) && (v[v1] == 0 || v[route] + 1 < v[v1])) { v[v1] = v[route] + 1; q.push(v1); } if ((0 < v2) && (v[v2] == 0 || v[route] + 1 < v[v2])) { v[v2] = v[route] + 1; q.push(v2); } } if (result == 0) { cout << -1; } else { cout << result; } return 0; } inline int main045() { int num; int *value; int **c_value; int i; cin >> num; value = new int[num]; c_value = new int*[num]; for (i = 0; i < num; i++) { cin >> value[i]; c_value[i] = new int[2]; } c_value[0][0] = 0; c_value[0][1] = value[0]; if (num > 1) { c_value[1][0] = value[0]; c_value[1][1] = value[1]; } for (i = 2; i < num; i++) { c_value[i][0] = max(c_value[i - 1][1], c_value[i - 2][1]); c_value[i][1] = max(c_value[i - 1][0] + value[i], c_value[i - 2][0] + value[i]); } cout << max(c_value[num - 1][0], c_value[num - 1][1]); return 0; }