#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //方針 //N<=10^3なので使うor使わないの全探索はO(2^N)なので無理 //動的計画法を用いる //dp[N+1][use] //N個目まで調べた時Nを使った時の美味しさの和最大とNを使ってない時の最大 int main(){ int N; cin >> N; //dp int dp[N+1][2]; FOR(i, 0, N+1) FOR(j, 0, 2) dp[i][j] = -1; dp[0][0] = 0; //動的計画法 FOR(i, 0, N){ int v; cin >> v; //実際はif必要ない //一個前が使用していないなら使ってもいいし使わなくてもいい if(dp[i][0]>=0){ dp[i+1][0] = max(dp[i+1][0], dp[i][0]); dp[i+1][1] = max(dp[i+1][1], dp[i][0] + v); } //一個前が使用してたら次使用しない if(dp[i][1]>=0){ dp[i+1][0] = max(dp[i+1][0], dp[i][1]); } } cout << max(dp[N][0], dp[N][1]) << endl; }