Problem Link

很简单的一道 D 题。

Explanation

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

Solution

很显然这是一道 DP 题。

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

接下来分类讨论：

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

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

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

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

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

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

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

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

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

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

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

结论如下；

当 xi=0x_i=0 时：

{fi,0=max⁡(fi−1,0,fi−1,0+yi,fi−1,1+yi)fi,1=fi−1,1\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}

当 xi=1x_i=1 时：

{fi,0=fi−1,0fi,1=max⁡(fi−1,1,fi−1,0+yi)\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⁡(fn,0,fn,1)\max(f_{n,0},f_{n,1}) 即可。

Core Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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]));