AT_ABC306D 题解

Problem Link

很简单的一道 D 题。

Explanation

高桥君要在餐厅里吃一份由 $n$ 道菜组成的奇怪的全套菜单，每道菜都有一个美味程度 $y_i$，但是有的菜含有毒素，有的菜含有解毒剂。高桥君可以选择吃或者不吃每道菜，但是如果他吃了毒素，他会拉肚子，如果他拉肚子时再吃毒素，他会死亡。高桥君必须活着离开餐厅，求他能够得到的最大的美味程度之和。

Solution

很显然这是一道 DP 题。

设 $f_{i,1/0}$ 表示吃到第 $i$ 道菜时，当前是否中毒的最大美味值。

接下来分类讨论：

• 如果当前这一步为无毒，即 $x_i=0$ 时：

  • 考虑 $f_{i,1}$：要想保持中毒状态，当前这一步一定不能吃，即 $f_{i,1}=f_{i-1,1}$；

  • 否则，考虑 $f_{i,0}$：要想在这一步吃完不是中毒状态，有两种可能：

    1. 前一步本来就不是中毒状态，那直接取当前吃与不吃的最大值即可，即 $f_{i,0}=\max(f_{i-1,0},f_{i-1,0}+y_i)$；
    2. 前一步是中毒状态，那这一步必须吃，才能使吃完后状态为无毒，即 $f_{i,0}=f_{i-1,1}+y_i$。

    所以，综合一下上式， $f_{i,0}=\max(f_{i-1,0},f_{i-1,0}+y_i,f_{i-1,1}+y_i)$。

• 否则，如果当前这一步有毒，即 $x_i=1$ 时：

  • 仍然像之前一样，先考虑 $f_{i,1}$ 情况：也就是这一步吃完时中毒状态，出现两种可能：

    1. 之前本来就中毒，这一步没有吃，注意，没有之前中毒，这一步还吃的状态，因为这样会使高桥死亡，$f_{i,1}=f_{i-1,1}$；

    2. 当然，也有可能之前没有中毒，吃了以后中毒了，也就是 $f_{i,1}=f_{i-1,0}+y_i$。

    综合一下，就是 $f_{i,1}=\max(f_{i-1,1},f_{i-1,0}+y_i)$。

  • 接着考虑 $f_{1,0}$：要想当前不中毒，只能不吃当前这一步。即 $f_{i,0}=f_{i-1,0}$。

---

结论如下；

当 $x_i=0$ 时：

$$\begin{cases} f_{i,0}=\max(f_{i-1,0},f_{i-1,0}+y_i,f_{i-1,1}+y_i)\\ f_{i,1}=f_{i-1,1} \end{cases}$$

当 $x_i=1$ 时：

$$\begin{cases} f_{i,0}=f_{i-1,0}\\ f_{i,1}=\max(f_{i-1,1},f_{i-1,0}+y_i) \end{cases}$$

最后输出 $\max(f_{n,0},f_{n,1})$ 即可。

Core Code

f[0][0]=f[0][1]=0;
for(int i=1;i<=n;i++)
{
	if(x[i]==1)
	{
		f[i][1]=max(f[i-1][1],f[i-1][0]+y[i]);
		f[i][0]=f[i-1][0];
	}
	else
	{
        f[i][1]=f[i-1][1];
		f[i][0]=max(f[i-1][1]+y[i],max(f[i-1][0]+y[i],f[i-1][0]));
	}
}
write(max(f[n][0],f[n][1]));