[Atcoder] ABC306 :: D - Poisonous Full-Course

DP로 해결할 수 있는 문제이다.
각 음식은 0과 1로 주어지는데, 연속해서 1을 먹을 수가 없다고 한다. 그리고 음식을 먹지 않고 skip을 할 수도 있다. 
1을 먹은 상태에서 0을 먹으면 상태가 0으로 변한다. 그래서 직관적으로 0인 음식은 무조건 먹으면 되겠네.. 싶지만 음수가 주어질 수도 있다.

따라서 최근 먹은 음식이 0인지 1인지의 경우의 수로 나누고 점화식을 세워볼 수 있다.

DP[i][j] = i 상태이고 j번째 음식까지 먹었을때의 최댓값으로 설정하자.
그다음 각 음식의 상태에 따라 점화식을 2개 만들 수 있는데, 현재 음식이 0인 경우와 1인 경우로 나눠보자. 
현재 i번째 음식이 0이라면, DP[0][i-1], DP[1][i-1] 중 최댓값과 현재 음식의 만족도를 더한 값을 DP[0][i]에 갱신해주면 된다. 이때 i 음식의 만족도가 음수일 수도 있으므로 DP[0][i-1]도 DP[0][i]의 후보가 될 수 있다.

현재 i번째 음식이 1이라면, DP[0][i-1] 음식만 정답의 후보가 될 수 있다. 왜냐면 1을 연속해서 먹을 수 없기 때문이다. 그리고 i번째 음식이 음수일 수도 있으므로, skip한 경우도 정답의 후보로 추가할 수 있다.

이 점화식을 구현하면 된다. 

#include<iostream>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
int N;
ll DP[2][300010], foods[300010];
bool isOk[300010];


int main() {
    memset(isOk, false, sizeof(isOk));
    memset(DP, 0, sizeof(DP));
    cin >> N;
    for (int i=1; i<=N; i++) {
        int x, y;
        cin >> x >> y;
        if (x == 0) isOk[i] = true;
        foods[i] = y;
    }
    
    for (int i=1; i<=N; i++) {
        if (isOk[i]) {
            DP[0][i] = max({DP[0][i-1] + foods[i], DP[1][i-1] + foods[i], DP[0][i-1]});
            DP[1][i] = DP[1][i-1];
        } else {
            DP[1][i] = max({DP[0][i-1] + foods[i], DP[1][i-1]});
            DP[0][i] = max({DP[0][i-1]});
        }
    }
    cout << max(DP[0][N], DP[1][N]) << '\n';
}