状態をまとめる事でDPできる. 遷移に影響するのは,
- 今の料理が解毒剤入りか
- 今まで食べた美味しさの合計
のみであり,それまでお腹を壊したか否かの状態列は無関係. つまり状態をまとめる事が出来る.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll x(n), y(n);
rep(i,n){
cin >> x[i] >> y[i];
}
vll dp(2, -INFL);
dp[0] = 0;
rep(i,n){
vll old(2, -INFL);
swap(dp, old);
chmax(dp[0], old[0]);
chmax(dp[1], old[1]);
if(x[i] == 0){
chmax(dp[0], old[0] + y[i]);
chmax(dp[0], old[1] + y[i]);
}else{
chmax(dp[1], old[0] + y[i]);
}
}
cout << max(dp[0], dp[1]) << endl;
return 0;
}