Official

D - Poisonous Full-Course Editorial by en_translator


Consider solving this problem with a Dynamic Programming (DP). What store should we maintain?

Going straight to the point, the problem can be solved by filling the following DP table.

  • \(dp[\) course \(i\) \(][\) Takahashi’s state \(j\) \(]\)
    • The maximum total tastiness of the courses that he has eaten when he has decided whether to eat or skip for the first \(i\) courses and his state is \(j\) (\(0\) … he has an healthy stomach, \(1\) … he has an upset stomach.)

If you could not solve this problem, given “how the DP table can be defined” above, try implementing while considering “how the transitions should be.” It is a good exercise of DP.

Explanation of transitions

  // Note that 0-based indices are used for the courses in the sample code
  // Initialize the DP table
  for(long long i=0;i<=n;i++){
    dp[i][0]=-4e18; // dp[i][0] = -∞
    dp[i][1]=-4e18; // dp[i][1] = -∞
  }
  dp[0][0]=0; // Initially, he has a healthy stomach

  for(long long i=0;i<n;i++){
    // Transition for his choice of eating the i-th course
    if(x[i]==0){
      dp[i+1][0]=max(dp[i][0],max(dp[i][0],dp[i][1])+y[i]);
    }
    else{
      dp[i+1][1]=max(dp[i][1],dp[i][0]+y[i]);
    }
    // Transition for his choice of skipping the i-th course
    dp[i+1][0]=max(dp[i+1][0],dp[i][0]);
    dp[i+1][1]=max(dp[i+1][1],dp[i][1]);
  }


Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

long long dp[300005][2];

int main(){
  long long n;
  cin >> n;
  vector<long long> x(n),y(n);
  for(long long i=0;i<n;i++){
    cin >> x[i] >> y[i];
  }

  for(long long i=0;i<=n;i++){
    dp[i][0]=-4e18;
    dp[i][1]=-4e18;
  }
  dp[0][0]=0;

  for(long long i=0;i<n;i++){
    if(x[i]==0){
      dp[i+1][0]=max(dp[i][0],max(dp[i][0],dp[i][1])+y[i]);
    }
    else{
      dp[i+1][1]=max(dp[i][1],dp[i][0]+y[i]);
    }

    dp[i+1][0]=max(dp[i+1][0],dp[i][0]);
    dp[i+1][1]=max(dp[i+1][1],dp[i][1]);
  }
  cout << max(dp[n][0],dp[n][1]) << "\n";
  return 0;
}

posted:
last update: