動的計画法でこの問題を解くことを考えます。すると、どのような情報を保持するべきでしょうか？

結論から言うと、以下の DP テーブルを作成することでこの問題を解くことができます。

• \(dp[\) 料理 \(i\) \(][\) 高橋くんの状態 \(j\) \(]\)
  • 料理 \(i\) までの料理を食べるか下げてもらうか選択した時に、高橋くんの状態が \(j\) ( \(0\) … 高橋くんがお腹を壊していない、 \(1\) … 高橋くんがお腹を壊している ) である時の、食べた料理の美味しさの総和の最大値

この問題が解けなかった方は、上で 「どのような DP テーブルを作れば解けるか」を示したので、「 DP テーブルの遷移はどうするべきか」を考えて実装してみてください。動的計画法の良い練習になります。

  // 実装例では料理を 0-indexed で取り扱っていることに注意
  // DP テーブルの初期化
  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; // 最初、高橋くんはお腹を壊していない

  for(long long i=0;i<n;i++){
    // 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]);
    }
    // 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]);
  }

#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;
}