[C++] BJO 2156 : 포도주 시식

문제

https://www.acmicpc.net/problem/2156

 

 

 

풀이

연속 3개의포도주를 마실 수 없기 때문에 이 부분을 고려해 점화식을 세운다.

자세한 내용은 코드를 참고하면 된다.

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

long n, ans;
long grape[10001];
long dp[10001];
int main() {
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> grape[i];
    }
    dp[0] = grape[0];
    dp[1] = grape[1]+grape[0];
    dp[2] = max(grape[0]+grape[2], grape[1]+grape[2]);

    ans = max(dp[1], dp[2]);
    
    for(int i=3; i<n; i++){
        dp[i] = max(dp[i-2]+grape[i]  , dp[i-3]+grape[i-1]+grape[i]);
        if(i >= 4){
            dp[i] = max(dp[i], grape[i]+grape[i-1]+dp[i-4]);
        }
        dp[i] = max(dp[i-1], dp[i]);
        ans = max(dp[i], ans);
    }
    cout << ans << "\n";
    return 0;
}