题目大意
Takahashi 要品尝 \(N\) 个菜品.这些菜品中有些是有毒的,有些是解药.当他吃下第 \(i\) 个菜品时,他的总美味值会增加 \(Y_{i}\) ,同时有以下效果:
-
如果吃下的菜品是有毒的( \(X_{i}=1\) ),且他现在的胃是健康的,他的胃转变为不舒服的;如果他现在的胃已经是不舒服的了,他就死了.
-
如果吃下的菜品是解药( \(X_{i}=0\) ),且他现在的胃是健康的,什么也不会发生;如果他现在的胃是不舒服的,他的胃转变为健康的.
现在, Takahashi 面临每一个送上来的菜品,可以选择吃或者不吃.他要活着离开餐厅,并使总美味值最大.
思路
使用dp.使用 $f[i][0/1] $ 表示面临过i个菜品后,他的胃的状态对应的最大总美味值.
状态转移式如下:
-
如果\(x_{i}=1\) , $$f[i][0]=f[i-1][0]$$ $$f[i][1]=max(f[i-1][0]+y_{i} \space,f[i-1][1])$$
-
如果\(x_{i}=0\) , $$f[i][0]=max(f[i-1][0],f[i-1][0]+y_{i}\space ,f[i-1][1]+y_{i}\space )$$ $$f[i][1]=f[i-1][1]$$
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,x[300001],y[300001];
long long f[300001][2];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
if(x[1]) {f[1][0]=0;f[1][1]=y[1];}
else {f[1][0]=max(0,y[1]);}
for(int i=2;i<=n;i++)
{
if(x[i])
{
f[i][1]=max(f[i-1][0]+y[i],f[i-1][1]);
f[i][0]=f[i-1][0];
}
else
{
f[i][1]=f[i-1][1];
f[i][0]=max(max(f[i-1][0],f[i-1][0]+y[i]),f[i-1][1]+y[i]);
}
}
cout<<max(f[n][1],f[n][0])<<endl;
return 0;
}