D - Poisonous Full-Course-AtCoder Beginner Contest 306

本文主要是介绍D - Poisonous Full-Course-AtCoder Beginner Contest 306，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

D - Poisonous Full-Course

题意：

给出n道菜，标记为0表示无毒，或解药，标记为1表示有毒。
每道菜有一个美味值，求不被毒死能够获得的最大美味值。
不被毒死有以下方法：
1.选择0号菜品。
2.选择1号菜品后选择0号菜品解毒。
注意每一份菜品非必选，可以跳过。

分析：

这是一道dp题，可以这样定义dp：
int dp[MAXN][2];
dp[i][j]表示走完前i道菜品，当前状态为j的最大美味值。
那么状态转移方程分析：
对于每一道菜有以下两种情况:

Case1：当前菜0无毒：
//dp[i][0]=max(有毒状态选中解毒，无毒状态选中保持无毒，不选保持无毒)；
dp[i][0]=max(max(dp[i-1][1]+tas[i],dp[i-1][0]+tas[i]),dp[i-1][0]);
//dp[i][1],当前无毒，不会改变，和dp[i-1][1]相同
dp[i][1]=dp[i-1][1];

Case2：当前菜1有毒：
//dp[i][0]当前菜有毒所以不变
dp[i][0]=dp[i-1][0];
//dp[i][1]=max(保持有毒状态不选这道菜，上一个无毒状态选中这道菜)
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+tas[i]);

代码：

#include<iostream>
using namespace std;
#define int long long
const int MAXN=1e6+5;
int dp[MAXN][2];/*dp[i][j]表示走完前i道菜品，当前状态为j的最大美味值*/
signed main()
{int n;cin>>n;int poi[n+2],tas[n+2];for(int i=1;i<=n;i++){cin>>poi[i]>>tas[i];}for(int i=1;i<=n;i++){if(poi[i]==1){dp[i][1]=max(dp[i-1][1],dp[i-1][0]+tas[i]);dp[i][0]=dp[i-1][0];}else{dp[i][0]=max(max(dp[i-1][1]+tas[i],dp[i-1][0]+tas[i]),dp[i-1][0]);dp[i][1]=dp[i-1][1];}}cout<<max(dp[n][0],dp[n][1])<<endl;
}