补题 [ABC306D] 有毒套餐

题目描述

高橋先生在一家餐厅点了一道奇怪的有毒套餐，它由 $ N $ 道菜组成。
这道套餐中的第 $ i $ 道菜具有以下特点：

  • 如果 $ X_i=0 $，则这道菜是一道 解毒剂，其美味度为 $ Y_i $。
  • 如果 $ X_i=1 $，则这道菜是一道 有毒菜，其美味度为 $ Y_i $。

高橋先生吃了这些菜之后，他的状态会按照以下规则变化：

  • 初始时，高橋先生的胃并未受损。
  • 当高橋先生 胃未受损 时，
    • 如果他吃了一道 解毒剂，他仍然 胃未受损。
    • 如果他吃了一道 有毒菜，他将 胃受损。
  • 当高橋先生 胃受损 时，
    • 如果他吃了一道 解毒剂，他将恢复到 胃未受损 的状态。
    • 如果他吃了一道 有毒菜，他将 死亡。

套餐的流程如下：

  • 对于 $ i\ =\ 1,\ \ldots,\ N $，按照顺序进行以下步骤：
    • 首先，上菜员将第 $ i $ 道菜上给高橋先生。
    • 接下来，高橋先生选择是 吃掉 还是 拒绝 这道菜。
      • 如果选择 吃掉，高橋先生将吃掉第 $ i $ 道菜。同时他的状态也会相应地变化。
      • 如果选择 拒绝，高橋先生将不吃这道菜。他不能要求以后再上这道菜或以其他方式保存它。
    • 最后，（如果状态发生了变化）如果高橋先生还活着，
      • 如果 $ i\ \neq\ N $，则继续下一道菜。
      • 如果 $ i\ =\ N $，则高橋先生活着离开餐厅。

由于高橋先生之后有重要的事情要做，他必须活着离开餐厅。
在满足这个条件的前提下，对于高橋先生对每道菜的选择（吃掉或拒绝），请输出高橋先生可以选择的 **吃掉的

菜的美味度之和的最大值**（如果一道菜都不吃，则输出 $ 0 $）。

输入格式

输入按以下格式从标准输入给出。

$ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

输出格式

以整数形式输出答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
5
1 100
1 300
0 -200
1 500
1 300

样例输出 #1

1
600

样例 #2

样例输入 #2

1
2
3
4
5
4
0 -1
1 -2
0 -3
1 -4

样例输出 #2

1
0

样例 #3

样例输入 #3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

样例输出 #3

1
4100000000

提示

约束

  • 输入均为整数。
  • $ 1\ \le\ N\ \le\ 3\ \times\ 10^5 $
  • $ X_i\ \in\ \{0,1\} $
    • 也就是说， $ X_i $ 只能是 $ 0 $ 或 $ 1 $。
  • $ -10^9\ \le\ Y_i\ \le\ 10^9 $

样例解释 1

通过以下选择，可以使得吃掉的菜的美味度之和达到 $ 600 $，这是可以考虑的最大值。 - 拒绝第一道菜。高橋先生的胃没有受损。 - 吃掉第二道菜。高橋先生的胃受损，吃掉的菜的美味度之和为 $ 300 $。 - 吃掉第三道菜。高橋先生恢复到未受损的状态，吃掉的菜的美味度之和为 $ 100 $。 - 吃掉第四道菜。高橋先生的胃受损，吃掉的菜的美味度之和为 $ 600 $。 - 拒绝第五道菜。高橋先生的胃受损。 - 最后，高橋先生还活着，所以他离开餐厅时是活着的。

样例解释 2

对于这个输入，不吃任何菜是最佳选择，但此时答案为 $ 0 $。

样例解释 3

答案可能超过 $ 32 $ 位有符号整数的范围。

题解

题目解析

这道题说实话是挺简单的,把所有可能都dp到就可以,但是为什么当时比赛时没有想到…

我们设:

1
2
dp[i][1] := 吃前i道菜最后保持1状态的最大美味度之和
dp[i][0] := 吃前i道菜最后保持0状态的最大美味度之和

接下来是最重要的分析每种可能的递推方法,也就是状态转移方程.

我这里提一下,dp的实质就是在之前的状态下进行递推转移,我们分析状态转移方程的时候仅需要剥离出其中某一时刻的所有状态,然后把所有的状态找到与之相关的前一状态的转移过程递推式就好了.

我们剥离出来了 前i个食物 这一时间节点,这一时间节点拥有两个状态:

  • 此时他是健康的
  • 此时他是中毒的

根据这两个状态,我们需要分别推导它们是怎么由上一状态转移过来的:

  • 此时他是健康的:

    1
    2
    3
    4
    也就是dp[i][0]:
    1. 它可以由之前i-1节点时就是健康的不吃东西转移过来.
    2. 它可以由之前i-1节点时就是健康的然后吃了解药转移过来.
    3. 它可以由之前i-1节点生病,但第i个节点是解药,吃了解药转移过来.

  • 此时他是中毒的:

    1
    2
    3
    也就是dp[i][1]:
    1. 它可以由之前i-1节点时就是生病的然后不吃东西转移过来.
    2. 它可以由之前i-1节点健康,但第i个节点是有毒的食物,吃了有毒的食物转移过来.

然后我们就得到了状态转移方程,根据方程我们写代码就可以AC了.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(3e5);
ll dp[MAXN][2],a[MAXN][3];

signed main(){
	int n;
	cin >> n;
	fa(1,n,1){
		cin >> a[i][1] >> a[i][2];
	}
	fa(1,n,1){
		if(a[i][1] == 1){
			dp[i][1] = max(dp[i-1][1],dp[i-1][0]+a[i][2]);
			dp[i][0] = dp[i-1][0];
		}else{
			dp[i][1] = dp[i-1][1];
			dp[i][0] = max(dp[i-1][0],max(dp[i-1][1]+a[i][2],dp[i-1][0]+a[i][2]));
		}
	}
    cout << max(dp[n][1],dp[n][0]) << endl;
    return 0;
}